题目描述

给定线性递推式$f(n)=a_1f(n-1)+a_2f(n-2)+…+a_df(n-d),(n>d)$，请求出其第$n$项在模$m$意义下的值是多少。

输入格式

第一行输入三个整数$d,n,m$。 第二行输入$d$个整数$a_1,a_2,…,a_d$。 第三行输入$d$个整数$f(1),f(2),…,f(d)$，为数列初始值。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

2 10 100
1 1
1 1

样例输出 #1

55

说明/提示

有$1\leq d\leq 15,1\leq n,m<2^{31},1\leq a_i,f(i)\leq 10^4$。