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:

{F[1][1]=1F[i][j]=a×F[i][j−1]+bj≠1F[i][1]=c×F[i−1][m]+di≠1

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 1000000007.

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 1000000007.

Sample Input

Copy
3 4 1 3 2 6

Sample Output

Copy
85

Explanation

The matrix in the example is:

(147102629323576798285)

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≤103; 1≤a,b,c,d≤109
4
5 1≤n,m≤109; 1≤a=c≤109; 1≤b=d≤109
6 1≤n,m≤109; a=c=1; 1≤b,d≤109
7 1≤n,m,a,b,c,d≤109
8
9
10
11 1≤n,m≤101000; a=c=1; 1≤b,d≤109
12 1≤n,m≤101000; 1≤a=c≤109; 1≤b=d≤109
13 1≤n,m≤101000; 1≤a,b,c,d≤109
14
15 1≤n,m≤1020000; 1≤a,b,c,d≤109
16
17 1≤n,m≤101000000; a=c=1; 1≤b,d≤109
18 1≤n,m≤101000000; 1≤a=c≤109; 1≤b=d≤109
19 1≤n,m≤101000000; 1≤a,b,c,d≤109
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.