Description

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

Input Format

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

Output Format

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

3 4 1 3 2 6

85

Hint

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

Translated by ChatGPT 5