### National Olympiad in Informatics, China, 2013

## Day 2, Problem 1 - Matrix Game

TingTing is a girl that loves matrices. One day, she wants to use a computer to generate a giant `n` row by `m` column matrix (you don't have to worry about how she'll store it). Her generated matrix will satisfy a mystical property: if we use `F`[`i`][`j`] to represent the cell in the `i`-th row and `j`-th column, then `F`[`i`][`j`] will satisfy the following system of equations:

where `a`, `b`, `c`, and `d` are given constants.

TingTing would like to know the value of `F`[`n`][`m`] and she would like you to help her. Since the final value may be very large, you are only required to output it modulo 1,000,000,007.

### Input Format

The input will contain the six integers `n`, `m`, `a`, `b`, `c`, and `d`.

### Output Format

Output a single integer, the value of `F`[`i`][`j`] modulo 1,000,000,007.

### Sample Input

3 4 1 3 2 6

### Sample Output

85

### Explanation

The matrix in the example is:

### Constraints

Test Case | Constraints |
---|---|

1 | 1 ≤ n, m ≤ 10; 1 ≤ a, b, c, d ≤ 1000 |

2 | 1 ≤ n, m ≤ 100; 1 ≤ a, b, c, d ≤ 1000 |

3 | 1 ≤ n, m ≤ 10^{3}; 1 ≤ a, b, c, d ≤ 10^{9} |

4 | |

5 | 1 ≤ n, m ≤ 10^{9}; 1 ≤ a = c ≤ 10^{9}; 1 ≤ b = d ≤ 10^{9} |

6 | 1 ≤ n, m ≤ 10^{9}; a = c = 1; 1 ≤ b, d ≤ 10^{9} |

7 | 1 ≤ n, m, a, b, c, d ≤ 10^{9} |

8 | |

9 | |

10 | |

11 | 1 ≤ n, m ≤ 10^{1,000}; a = c = 1; 1 ≤ b, d ≤ 10^{9} |

12 | 1 ≤ n, m ≤ 10^{1,000}; 1 ≤ a = c ≤ 10^{9}; 1 ≤ b = d ≤ 10^{9} |

13 | 1 ≤ n, m ≤ 10^{1,000}; 1 ≤ a, b, c, d ≤ 10^{9} |

14 | |

15 | 1 ≤ n, m ≤ 10^{20,000}; 1 ≤ a, b, c, d ≤ 10^{9} |

16 | |

17 | 1 ≤ n, m ≤ 10^{1,000,000}; a = c = 1; 1 ≤ b, d ≤ 10^{9} |

18 | 1 ≤ n, m ≤ 10^{1,000,000}; 1 ≤ a = c ≤ 10^{9}; 1 ≤ b = d ≤ 10^{9} |

19 | 1 ≤ n, m ≤ 10^{1,000,000}; 1 ≤ a, b, c, d ≤ 10^{9} |

20 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 256M

**Added:** May 18, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...