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:

$\displaystyle \left\{\begin{matrix} F[1][1] = 1 \\ F[i][j] = a*F[i][j-1]+b && j \neq 1 \\ F[i][1] = c*F[i-1][m]+d && i \neq 1 \end{matrix}\right. $

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: $\textstyle \begin{pmatrix} 1 & 4 & 7 & 10 \\ 26 & 29 & 32 & 35 \\ 76 & 79 & 82 & 85 \end{pmatrix} $

Constraints

Test CaseConstraints
11 ≤ n, m ≤ 10; 1 ≤ a, b, c, d ≤ 1000
21 ≤ n, m ≤ 100; 1 ≤ a, b, c, d ≤ 1000
31 ≤ n, m ≤ 103; 1 ≤ a, b, c, d ≤ 109
4
51 ≤ n, m ≤ 109; 1 ≤ a = c ≤ 109; 1 ≤ b = d ≤ 109
61 ≤ n, m ≤ 109; a = c = 1; 1 ≤ b, d ≤ 109
71 ≤ n, m, a, b, c, d ≤ 109
8
9
10
111 ≤ n, m ≤ 101,000; a = c = 1; 1 ≤ b, d ≤ 109
121 ≤ n, m ≤ 101,000; 1 ≤ a = c ≤ 109; 1 ≤ b = d ≤ 109
131 ≤ n, m ≤ 101,000; 1 ≤ a, b, c, d ≤ 109
14
151 ≤ n, m ≤ 1020,000; 1 ≤ a, b, c, d ≤ 109
16
171 ≤ n, m ≤ 101,000,000; a = c = 1; 1 ≤ b, d ≤ 109
181 ≤ n, m ≤ 101,000,000; 1 ≤ a = c ≤ 109; 1 ≤ b = d ≤ 109
191 ≤ n, m ≤ 101,000,000; 1 ≤ a, b, c, d ≤ 109
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...