时间限制：1秒　　内存限制：256M

---

【问题描述】

　　\(Fibonacci\) 数列：\(f(n)=f(n-2)+f(n-1)\)，就是一个 2 阶常系数线性递推关系，由此我们得出 \(k\) 阶常系数线性递推关系的一般形式：\(f(n)=\sum_{i=1}^{k}a_i*f(n-i)\)，其中 \(n>k\) 且 \(a_1,a_2,…,a_k\) 是常数。

　　你的任务是对于给定的 \(k\) 阶线性递推式，求出它的第 \(n\) 项时多少？

【输入格式】

　　输入包含多组数据：
　　每组数据第一行为三个整数 \(k,n,m\)。
　　第二行为 \(k\) 个非负整数 \(a_1,a_2,…,a_k\)。
　　第三行为 \(k\) 个非负整数 \(f(1),f(2),…,f(k)\)。
　　输入结束标志为 \(k=m=n=0\)。

【输出格式】

　　对于每组数据，输出 \(f(n)\ mod\ m\) 的值。

【输入输出样例】

　Input

1 1 100
2
1
2 10 100
1 1
1 1
3 2147483647 12345
12345678 0 12345
1 2 3
0 0 0

　Output

1
55
423

【数据限制】

　　\(100\%\) 的数据，满足 \(1≤k≤15\)，\(1≤n≤10^9\)，\(1≤m≤46340\)，\(0≤a_i,f(i)≤2*10^9\)

【来源】

　　Mr.he