cho.shMatrix Game
F[i][j] = a*F[i-1][j] + b*F[i][j-1] + c*F[i-1][j-1] + d 형태의 점화식과 초기값이 주어질 때, n과 m이 10^1000000자리까지 커질 수 있는 상황에서 F[n][m]을 1e9+7로 나눈 나머지를 구한다.
어려움8행렬동적 계획법조합론수학아직 제출이 없습니다시간 제한1초메모리 제한512 MB문제
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.
입력
The input will contain the six integers n, m, a, b, c, and d.
출력
Output a single integer, the value of F[i][j] modulo 1,000,000,007.
제한
- 1 ≤
n,m≤ 101,000,000 - 1 ≤
a,b,c,d≤ 109