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

1

2 10 100

1 1

1 1

3 2147483647 12345

12345678 0 12345

1

55

423

Problem setter: Max Furlong

Special Thanks: Derek Kisman, EPS.

#include <stdio.h>
#include <string.h>
struct M {
    int v[16][16];
} o, I;
void mult(M &a, M &b, int m, int d) {
    static int i, j, k;
    static M t;
    t = o;
    for(i = 0; i < d; i++) {
        for(j = 0; j < d; j++) {
            for(k = 0; k < d; k++) {
                t.v[i][j] += a.v[i][k]*b.v[k][j];
                t.v[i][j] %= m;
            }
        }
    }
    a = t;
}
M solve(int n, int m, M base, int d) {
    M x = I, y = base;
    while(n) {
        if(n&1)
            mult(x, y, m, d);
        mult(y, y, m, d);
        n /= 2;
    }
    return x;
}
int main() {
    int d, n, m, a[16], f[16];
    int i;
    memset(&o, 0, sizeof(M));
    I = o;
    for(i = 0; i < 16; i++)
        I.v[i][i] = 1;
    while(scanf("%d %d %d", &d, &n, &m) == 3) {
        if(d == 0)
            break;
        for(i = 0; i < d; i++)
            scanf("%d", &a[i]), a[i] %= m;
        for(i = 0; i < d; i++)
            scanf("%d", &f[i]), f[i] %= m;
        M base = o, res;
        for(i = 0; i < d; i++)
            base.v[i][0] = a[i];
        for(i = 1; i < d; i++)
            base.v[i-1][i] = 1;

        res = solve(n-1, m, base, d);
        int ans = 0;
        for(i = 0; i < d; i++) {
            ans += res.v[i][d-1]*f[d-i-1];
            ans %= m;
        }
        printf("%lld\n", ans);
    }
    return 0;
}