Problem27128--递推关系

27128: 递推关系

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

考虑如下所示的递推关系:

f(n)=a1*f(n-1)+a2*f(n-2)+...+ad*f(n-d),对n>d

a1,a2,...,ad是任意常数。

一个著名的例子是Fibonacci数列:f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2),在这里d=2,a1=1,a2=1.

每一个这样的递推关系都由d(即递推的阶数),a1,a2,...,ad的值,f(1),f(2),...,f(d)的值唯一确定。给你这些值,和两个正整数n,m。你的任务是计算f(n)m的值。

Input

输入文件包含多组数据。

每组数据有3行:

1行是3个正整数d,n,m

2行是d个非负整数a1,a2,...,ad

3行是d个整数f(1),f(2),...,f(d)

两组数据之间由一个空行分隔。

Output

对每组数据,输出一行1个非负整数:f(n)m的值。

Sample Input Copy

1 1 100
2
1

2 10 100
1 1
1 1

3 2147483647 12345
12345678 0 12345
1 2 3

0 0 0

Sample Output Copy

1
55
423

HINT

数据组数<=150

对于100%的数据:

1<=d<=15

1<=n<=2^31-1

1<=m<=46340

所有的输入数据均在32位带符号整数范围内。

输入结束标志为d=n=m=0.

Source/Category