QuasiPolynomial Sum

All submissions for this problem are available.
You are given a polynomial P(X) = C_{D} * X^{D} + ... + C_{1} * X + C_{0} with integer coefficients C_{0}, C_{1}, ..., C_{D}. You are also given a nonnegative integer Q and positive integers M and N. Your task is to find the following sum
(P(0) * Q^{0} + P(1) * Q^{1} + ... + P(N − 1) * Q^{N − 1}) mod M.
Here A mod B means the remainder of the division of A by B.
Usually polynomials are given by the sequence of their coefficients. However, in this problem you will be given the sequence A_{0}, A_{1}, ..., A_{D}, where A_{i} = P(i) mod M, as an input. One can prove that these values are enough to restore the value of P(K) mod M for any integer K. Therefore, the value of the above sum is uniquely determined by the values M, Q, N, D, A_{0}, A_{1}, ..., A_{D}.
The function of the form P(X) * Q^{X} sometimes is called quasipolynomial, hence the title of the problem.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains four spaceseparated integers M, Q, N, D. The second line contains D + 1 spaceseparated integers A_{0}, A_{1}, ..., A_{D}.
Output
For each test case, output a single line containing the value of the corresponding sum.
Constraints
 1 ≤ T ≤ 5000
 1 < M < 10^{18}
 0 ≤ Q < M
 1 ≤ N < 10^{100000}
 0 ≤ D < 20000
 0 ≤ A_{i} < M for i = 0, 1, ..., D
 The sum of D + 1 over each input file does not exceed 20000.
 The overall number of digits in all numbers N in each input file does not exceed 10^{5}.
 M is not divisible by any number from 2 to D + 14, inclusive.
 It is guaranteed that there exists a polynomial P(X) of degree at most D with integer coefficients such that A_{i} = P(i) mod M for i = 0, 1, ..., D.
Example
Input: 2 101 2 5 0 1 289 1 6 2 1 4 9 Output: 31 91
Explanation
Example case 1. We have M = 101, Q = 2, N = 5, D = 0 and P(0) mod M = 1. Therefore, P(X) = C_{0} and P(0) mod 101 = 1. Hence, C_{0} mod 101 = 1. So we can take, for example, C_{0} = 1. Then the corresponding sum takes the form of (P(0) * Q^{0} + P(1) * Q^{1} + ... + P(N − 1) * Q^{N − 1}) mod M = (1 * 2^{0} + 1 * 2^{1} + 1 * 2^{2} + 1 * 2^{3} + 1 * 2^{4}) mod 101 = (1 + 2 + 4 + 8 + 16) mod 101 = 31 mod 101 = 31. Note, that the polynomial P(X) is not unique. We can take, for example, C_{0} = 102 or C_{0} = 2021. However, the same will be always the same.
Example case 2. We have M = 289, Q = 1, N = 6, D = 2 and P(0) mod M = 1, P(1) mod M = 4, P(2) mod M = 9. It is easy to see that we can take P(X) = (X + 1)^{2}. Then the corresponding sum takes the form of (1^{2} + 2^{2} + 3^{2} + 4^{2} + 5^{2} + 6^{2}) mod 289 = (1 + 4 + 9 + 16 + 25 + 36) mod 289 = 91. Note that the polynomial P(X) again is not unique. In fact, the set of all polynomials of degree at most 2 that satisfy the conditions P(0) mod 289 = 1, P(1) mod 289 = 4, P(2) mod 289 = 9 has the form of {(X + 1)^{2} + 289 * (C_{2} * X^{2} + C_{1} * X + C_{0})  C_{0}, C_{1}, C_{2} are integers}.
Author:  anton_lunyov 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/QPOLYSUM 
Tags  anton_lunyov dec12 hard math 
Date Added:  29102012 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions