Matrix Recursive Sequence

Tingting loves matrices. One day, she decided to generate a huge matrix with n rows and m columns (don’t worry about how she manages such a huge amount of data!). The matrix F has a magical property defined by the following recurrence:

\[ \begin{aligned} F[1, 1] &= 1,\\ F[i, j] &= a \times F[i, j-1] + b, &\text{for } j \neq 1, \\ F[i, 1] &= c \times F[i-1, m] + d, &\text{for } i \neq 1. \end{aligned} \]

Here, the symbols a, b, c, and d are given constants. Your task is to compute the value of F[n, m] modulo \(10^9+7\).

inputFormat

The input consists of a single line containing six space-separated integers: n, m, a, b, c, and d.

outputFormat

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

sample

1 1 1 1 1 1

1