Hide

Problem C
Linear Recurrences

Input

The first line of input contains an integer 1N40, the degree of the recurrence. The next line of input contains N+1 integers a0,a1,,aN indicating that the linear recurrence is xt=a0+i=1Naixti. The next line contains N integers x0,,xN1 giving the initial values for the recursion. All the coefficients a0,,aN and initial values x0,,xN1 are integers between 109 and 109 (inclusive).

The next line contains an integer 1Q10, the number of queries. Then follow Q lines of queries. Each query consists of two integers T, M where 0T1018 gives the index and 1M109 is a moduli.

Output

For each query T, M, output a line containing xTmodM.

Sample Input 1 Sample Output 1
2
0 1 1
0 1
6
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
1
1
2
3
5
8
Sample Input 2 Sample Output 2
2
5 7 9
36713 5637282
4
1 10000
1375 1
3781 23
34683447233 1571385
7282
0
16
299255
Sample Input 3 Sample Output 3
3
1 2 3 4
0 0 0
1
42424242424242 1000000
552200
Hide

Please log in to submit a solution to this problem

Log in