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.