UVA

Problem A
Recurrences
Input: standard input
Output: standard output

Consider recurrent functions of the following form:

f(n) = a₁ f(n - 1) + a₂ f(n - 2) + a₃ f(n - 3) + ... + a_d f(n - d), for n > d.
a₁, a₂, ..., a_d - arbitrary constants.

A famous example is the Fibonacci sequence, defined as: f(1) = 1, f(2) = 1, f(n) = f(n - 1) + f(n - 2). Here d = 2, a₁ = 1, a₂ = 1.

Every such function is completely described by specifying d (which is called the order of recurrence), values of d coefficients: a₁, a₂, ..., a_d, and values of f(1), f(2), ..., f(d). You'll be given these numbers, and two integers n and m. Your program's job is to compute f(n) modulo m.

Input

Input file contains several test cases. Each test case begins with three integers: d, n, m, followed by two sets of d non-negative integers. The first set contains coefficients: a₁, a₂, ..., a_d. The second set gives values of f(1), f(2), ..., f(d).

You can assume that: 1 <= d <= 15, 1 <= n <= 2³¹ - 1, 1 <= m <= 46340. All numbers in the input will fit in signed 32-bit integer.

Input is terminated by line containing three zeroes instead of d, n, m. Two consecutive test cases are separated by a blank line.

Output

For each test case, print the value of f(n) (mod m) on a separate line. It must be a non-negative integer, less than m.

Sample Input Output for Sample Input

1 1 100

2 10 100

1 1

1 1

3 2147483647 12345

12345678 0 12345

1 2 3

0 0 0

sl: 比较裸的快速幂。拿来练练手，主要是代码。

1 // by caonima
2 // hehe
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 using namespace std;
8 const int MAX= 1e5+10;
9 typedef long long LL;
10 typedef vector<LL> vec;
11 typedef vector<vec> mat;
12 LL a[MAX],f[MAX];
13 LL d,n,m;
14
15 mat mul(mat &A,mat &B) {
16     mat C(A.size(),vec(B[0].size(),0));
17     for(int i=0;i<A.size();i++) {
18         for(int k=0;k<B.size();k++) {
19             for(int j=0;j<B[0].size();j++) {
20                 C[i][j]=(C[i][j]+A[i][k]*B[k][j])%m;
21             }
22         }
23     }
24     return C;
25 }
26
27 mat pow(mat A, LL n) {
28     mat B(A.size(),vec(A.size(),0));
29     for(int i=0;i<A.size();i++) B[i][i]=1;
30     while(n>0) {
31         if(n&1) B=mul(A,B);
32         A=mul(A,A);
33         n>>=1;
34     }
35     return B;
36 }
37
38 int main() {
39     while(scanf("%lld %lld %lld",&d,&n,&m)==3&&(d||n||m)) {
40         for(int i=0;i<d;i++) {
41             scanf("%lld",&a[i]);
42         }
43         for(int i=0;i<d;i++) {
44             scanf("%lld",&f[i]);
45         }
46         mat A(d,vec(d,0));
47         vec B(d,0);
48         for(int i=0;i<d;i++) A[0][i]=a[i];
49         for(int i=1;i<d;i++) A[i][i-1]=1;
50         for(int i=0;i<d;i++) B[i]=f[i];
51         A=pow(A,n-d);
52         LL ans=0;
53         for(int i=0;i<d;i++) {
54             ans=(ans+(LL)A[0][i]*B[d-i-1])%m;
55         }
56         printf("%lld ",ans);
57     }
58     return 0;
59 }