一个由自然数组成的数列按下式定义：

对于i <= k：a_i = b_i

对于i > k: a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k

其中b_j和 c_j （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算a_m + a_m+1 + a_m+2 + ... + a_n, 并输出它除以给定自然数p的余数的值。

由四行组成。

第一行是一个自然数k。

第二行包含k个自然数b₁, b₂,...,b_k。

第三行包含k个自然数c₁, c₂,...,c_k。

第四行包含三个自然数m, n, p。

仅包含一行：一个正整数，表示(a_m + a_m+1 + a_m+2 + ... + a_n) mod p的值。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

int n;

ll p , sum[20];

struct data

{

	ll v[20][20];

	data() {memset(v , 0 , sizeof(v));}

	data operator*(const data a)const

	{

		data ans;

		int i , j , k;

		for(i = 1 ; i <= n ; i ++ )

			for(j = 1 ; j <= n ; j ++ )

				for(k = 1 ; k <= n ; k ++ )

					ans.v[i][j] = (ans.v[i][j] + v[i][k] * a.v[k][j]) % p;

		return ans;

	}

	data operator^(const ll a)const

	{

		data x = *this , ans;

		int y = a , i;

		for(i = 1 ; i <= n ; i ++ ) ans.v[i][i] = 1;

		while(y)

		{

			if(y & 1) ans = ans * x;

			x = x * x , y >>= 1;

		}

		return ans;

	}

}B , A;

ll cal(ll t)

{

	if(t < n) return sum[t];

	return (B * (A ^ (t - n + 1))).v[1][n];

}

int main()

{

	int i , j;

	ll l , r;

	scanf("%d" , &n);

	for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &B.v[1][i]) , B.v[1][n + 1] = B.v[1][n + 1] + B.v[1][i] , sum[i] = sum[i - 1] + B.v[1][i];

	for(i = n ; i >= 1 ; i -- ) scanf("%lld" , &A.v[i][n]) , A.v[i][n + 1] = A.v[i][n];

	for(i = 1 ; i < n ; i ++ ) A.v[i + 1][i] = 1;

	n ++ , A.v[n][n] = 1;

	scanf("%lld%lld%lld" , &l , &r , &p);

	for(i = 1 ; i < n ; i ++ ) sum[i] %= p;

	for(i = 1 ; i <= n ; i ++ )

		for(j = 1 ; j <= n ; j ++ )

			A.v[i][j] %= p , B.v[i][j] %= p;

	printf("%lld\n" , (cal(r) - cal(l - 1) + p) % p);

	return 0;

}