P1397 [NOI2013] Matrix Game

Tingting is a kid who likes matrices. One day she wants to use a computer to generate a huge matrix with $n$ rows and $m$ columns (you do not need to worry about how she stores it). The matrix she generates has a magical property: let $F[i, j]$ denote the element at row $i$, column $j$, then $F[i, j]$ satisfies the following recurrence: $$\begin{aligned} F[1, 1] &= 1 \\ F[i, j] &=a\times F[i, j-1]+b, &j\neq 1 \\ F[i, 1] &=c\times F[i-1, m]+d, &i\neq 1 \\ \end{aligned}$$ In the recurrence, $a, b, c, d$ are given constants. Now Tingting wants to know the value of $F[n, m]$. Please help her. Since the final result can be large, you only need to output the remainder of $F[n, m]$ modulo $10^9 + 7$.

One line containing six integers $n, m, a, b, c, d$. The meaning is as described above.

Output a single integer, the value of $F[n, m]$ modulo $10^9 + 7$.

Explanation for Sample 1. The matrix in the sample is: $$\begin{pmatrix} 1 & 4 & 7 & 10 \\ 26 & 29 & 32 & 35 \\ 76 & 79 & 82 & 85 \\ \end{pmatrix}$$ ### Constraints ::cute-table{tuack} | Test point ID | Constraints | | :-: | :-: | | 1 | $1 \le n,m \le 10$; $1 \le a,b,c,d \le 1000$ | | 2 | $1 \le n,m \le 100$; $1 \le a,b,c,d \le 1000$ | | 3 | $1 \le n,m \le 10^3$; $1 \le a,b,c,d \le 10^9$ | | 4 | $1 \le n,m \le 10^3$; $1 \le a,b,c,d \le 10^9$ | | 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 | $1 \le n,m,a,b,c,d \le 10^9$ | | 9 | $1 \le n,m,a,b,c,d \le 10^9$ | | 10 | $1 \le n,m,a,b,c,d \le 10^9$ | | 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 | $1 \le n,m \le 10^{1\,000}$; $1 \le a,b,c,d \le 10^9$ | | 15 | $1 \le n,m \le 10^{20\,000}$; $1 \le a,b,c,d \le 10^9$ | | 16 | $1 \le n,m \le 10^{20\,000}$; $1 \le a,b,c,d \le 10^9$ | | 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 | $1 \le n,m \le 10^{1\,000\,000}$; $1 \le a,b,c,d \le 10^9$ | Translated by ChatGPT 5