NOI '13 P4 - Matrix Game

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2013

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 \begin{cases}
F[1][1] = 1 \\
F[i][j] = a \times F[i][j-1]+b && j \ne 1 \\
F[i][1] = c \times F[i-1][m]+d && i \ne 1
\end{cases}

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 Specification

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

Output Specification

Output a single integer, the value of F[n][m] modulo 1\,000\,000\,007.

Sample Input

3 4 1 3 2 6

Sample Output

85

Explanation

The matrix in the example is:

\displaystyle \begin{pmatrix} 1 & 4 & 7 & 10 \\ 26 & 29 & 32 & 35 \\ 76 & 79 & 82 & 85 \end{pmatrix}

Constraints

Test Case Constraints
1 1 \le n, m \le 10; 1 \le a, b, c, d \le 1\,000
2 1 \le n, m \le 100; 1 \le a, b, c, d \le 1\,000
3 1 \le n, m \le 10^3; 1 \le a, b, c, d \le 10^9
4
5 1 \le n, m \le 10^9; 1 \le a = c \le 10^9; 1 \le b = d \le 10^9
6 1 \le n, m \le 10^9; a = c = 1; 1 \le b, d \le 10^9
7 1 \le n, m, a, b, c, d \le 10^9
8
9
10
11 1 \le n, m \le 10^{1\,000}; a = c = 1; 1 \le b, d \le 10^9
12 1 \le n, m \le 10^{1\,000}; 1 \le a = c \le 10^9; 1 \le b = d \le 10^9
13 1 \le n, m \le 10^{1\,000}; 1 \le a, b, c, d \le 10^9
14
15 1 \le n, m \le 10^{20\,000}; 1 \le a, b, c, d \le 10^9
16
17 1 \le n, m \le 10^{1\,000\,000}; a = c = 1; 1 \le b, d \le 10^9
18 1 \le n, m \le 10^{1\,000\,000}; 1 \le a = c \le 10^9; 1 \le b = d \le 10^9
19 1 \le n, m \le 10^{1\,000\,000}; 1 \le a, b, c, d \le 10^9
20

Problem translated to English by Alex.


Comments


  • 0
    maxcruickshanks  commented on Aug. 10, 2022, 4:21 a.m.

    Since the original data were weak, two additional test cases were added and weighted identically to the others, and all submissions were rejudged.