# #124. 【NOI2013】矩阵游戏

\begin{cases} F_{1,1} & = & 1 \\ F_{i,j} & = & a \cdot F_{i,j - 1} + b & j \neq 1 \\ F_{i,1} & = & c \cdot F_{i - 1,m} + d & i \neq 1 \end{cases}

### 样例一

#### input

3 4 1 3 2 6



#### output

85



#### explanation

$$\left(\begin{array}{cccc} 1 & 4 & 7 & 10\\ 26 & 29 & 32 & 35\\ 76 & 79 & 82 & 85 \end{array} \right)$$

### 限制与约定

1$1 \leq n, m \leq 10$；$1 \leq a, b, c, d \leq 1000$
2$1 \leq n, m \leq 100$；$1 \leq a, b, c, d \leq 1000$
3$1 \leq n, m \leq 10^3$；$1 \leq a, b, c, d \leq 10^9$
4$1 \leq n, m \leq 10^3$；$1 \leq a, b, c, d \leq 10^9$
5$1 \leq n, m \leq 10^9$；$1 \leq a = c \leq 10^9$；$1 \leq b = d \leq 10^9$
6$1 \leq n, m \leq 10^9$；$a = c = 1$；$1 \leq b, d \leq 10^9$
7$1 \leq n, m, a, b, c, d \leq 10^9$
8$1 \leq n, m, a, b, c, d \leq 10^9$
9$1 \leq n, m, a, b, c, d \leq 10^9$
10$1 \leq n, m, a, b, c, d \leq 10^9$
11$1 \leq n, m \leq 10^{1000}$；$a = c = 1$；$1 \leq b, d \leq 10^9$
12$1 \leq n, m \leq 10^{1000}$；$1 \leq a = c \leq 10^9$；$1 \leq b = d \leq 10^9$
13$1 \leq n, m \leq 10^{1000}$；$1 \leq a, b, c, d \leq 10^9$
14$1 \leq n, m \leq 10^{1000}$；$1 \leq a, b, c, d \leq 10^9$
15$1 \leq n, m \leq 10^{20000}$；$1 \leq a, b, c, d \leq 10^9$
16$1 \leq n, m \leq 10^{20000}$；$1 \leq a, b, c, d \leq 10^9$
17$1 \leq n, m \leq 10^{1000000}$；$a = c = 1$；$1 \leq b, d \leq 10^9$
18$1 \leq n, m \leq 10^{1000000}$；$1 \leq a = c \leq 10^9$；$1 \leq b = d \leq 10^9$
19$1 \leq n, m \leq 10^{1000000}$；$1 \leq a, b, c, d \leq 10^9$
20$1 \leq n, m \leq 10^{1000000}$；$1 \leq a, b, c, d \leq 10^9$