Sequence (a_i) of natural numbers is defined as follows:

a_i = b_i (for i <= k)
a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k (for i > k)

where b_j and c_j are given natural numbers for 1<=j<=k. Your task is to compute a_m + a_m+1 + a_m+2 + ... + a_n for given m <= n and output it modulo a given positive integer p.

Input

On the first row there is the number C of test cases (equal to about 50).
Each test contains four lines:
k - number of elements of (c) and (b) (1 <= k <= 15)

b₁,...,b_k - k natural numbers where 0 <= b_j <= 10⁹ separated by spaces

c₁,...,c_k - k natural numbers where 0 <= c_j <= 10⁹ separated by spaces

m, n, p - natural numbers separated by spaces (1 <= m <= n <= 10¹⁸, 1<= p <= 10⁸)

Output

Exactly C lines, one for each test case: (a_m + a_m+1 + a_m+2 + ... + a_n) modulo p.

Example

Input:
1
2
1 1
1 1
2 10 1000003

Output:
142