配置

20组数据,传统型,没有SpecialJudge。

背景

婷婷是个喜欢矩阵的小朋友。

描述

tangjz是个喜欢Fibonacci的小朋友,有一天他想用电脑生成一个巨大的n行m列的矩阵(你不用担心他如何存储),他称其为Fibonacci矩阵。他生成的这个矩阵满足一个神奇的性质,若用Fib[i][j]来表示矩阵中第i行第j列的元素,则Fib[i][j]满足下面的递推式:

\begin{cases} & Fib[1][1]=Fib[1][2]=1\\ & Fib[i][j]=a*Fib[i][j-2]+b*Fib[i][j-1]+c(2<j\leq m)\\ & Fib[i][1]=d*Fib[i-1][m-1]+e*Fib[i-1][m]+f (i\neq 1)\\ & Fib[i][2]=d*Fib[i-1][m]+e*Fib[i][1]+f(i\neq 1) \end{cases}

递推式中a, b, c, d, e, f都是给定的常数。

现在tangjz想知道Fib[n][m]的值是多少,请你帮助他。由于最终结果可能很大,你只需要输出Fib[n][m]对2012182013取模的值。

输入格式

八个用空格隔开的整数n, m, a, b, c, d, e, f,其中n, m, a, b, d, e为正整数,c, f为非负整数。

输出格式

一个整数,表示Fib[n][m]对2012182013取模的值。

样例输入1

3 4 1 1 0 1 1 0

样例输出1

144

样例解释1

样例中的矩阵为:\begin{pmatrix} 1 & 1 & 2 & 3\\ 5 & 8 & 13 & 21\\ 34 & 55 & 89 & 144 \end{pmatrix}

样例输入输出2

比赛数据包\fib_matrix\fib_matrix.in和fib_matrix.out

数据范围与约定

测试点编号

数据范围

1

n,m\leq10,a,b,c,d,e,f\leq100

2

n,m\leq100,a,b,c,d,e,f\leq1000

3

n,m\leq10^3,a=b=d=e=1,c=f=0

4

n,m\leq10^3,a=b=c=d=e=f=1

5

n,m\leq10^9,a=b=d=e=1,c=f=0

6

n,m\leq10^9,a=b=c=d=e=f=1

7

n,m,a,b,d,e\leq10^9,a=b,d=e,c=f=0

8

n,m,a,b,c,d,e,f\leq10^9,a=b,d=e,c=f

9

n,m,a,b,d,e\leq10^9,a=d,b=e,c=f=0

10

n,m,a,b,c,d,e,f\leq10^9,a=d,b=e,c=f

11

n,m\leq10^{1,000},a=b=d=e=1,c=f=0

12

n,m\leq10^{10,000},a=b=d=e=1,c=f=0

13

n,m\leq10^{10,000},a,b,c,d,e,f\leq10^9,a=d,b=e,c=f

14

n,m,a,b,c,d,e,f\leq10^{10,000},a=d,b=e,c=f

15

n,m,a,b,c,d,e,f\leq10^{100,000}

16

n,m,a,b,c,d,e,f\leq10^{100,000}

17

n,m,a,b,c,d,e,f\leq10^{1,000,000}

18

n,m,a,b,c,d,e,f\leq10^{1,000,000}

19

n,m,a,b,c,d,e,f\leq10^{1,000,000}

20

n,m,a,b,c,d,e,f\leq10^{1,000,000}