Tingting is a child who loves matrices. One day, she wants to use a computer to generate a huge $n \times m$ matrix (you don't need to worry about how she stores it). The matrix she generates satisfies a magical property: if we use $F[i][j]$ to represent the element in the $i$-th row and $j$-th column of the matrix, then $F[i][j]$ satisfies the following recurrence relations:

$$ \begin{cases} 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{cases} $$

In the recurrence relations, $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 may be very large, you only need to output the remainder of $F[n][m]$ divided by $1,000,000,007$.

Input

The input contains one line with six integers $n, m, a, b, c, d$. The meanings are as described above.

Output

Output one integer, representing the remainder of $F[n][m]$ divided by $1,000,000,007$.

Examples

Input 1

3 4 1 3 2 6

Output 1

85

Note 1

The matrix in the example is: $$ \begin{pmatrix} 1 & 4 & 7 & 10 \\ 26 & 29 & 32 & 35 \\ 76 & 79 & 82 & 85 \end{pmatrix} $$

Input 2

See Download Files: matrix.in and matrix.out.

Constraints