Power Sums

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has n nonnegative integers a_{1}, a_{2}, ..., a_{n}. He defined the following function f(k) = (a_{1}^{k} + a_{2}^{k} + ... + a_{n}^{k}) mod (10^{9} + 7) over them.
Chef knows the values f(1), f(2), ..., f(n), but he has forgotten the values a_{1}, a_{2}, ..., a_{n}.
Now Chef wants to evaluate the function f over some integers (total Q of them), can you please help him in this?
Input
The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
Each test case consists of three lines.
The first line contains two space separated integers n and Q.
The second line contains n space separated integers  the values of f(1), f(2), ..., f(n).
The third line contains Q space separated integers x_{1}, x_{2}, ..., x_{q}, where x_{i} denotes the number in the ith query.
Output
For each test case, print a single line containing Q space separate integers denoting the values of f(x_{1}), f(x_{2}), ..., f(x_{q}).
Constraints
 1 ≤ n ≤ 300
 1 ≤ Q ≤ 30
 0 ≤ f(i) < 10^{9} + 7
 n < x_{i} ≤ 10^{18}
 It is guaranteed that given information is enough to restore the function f and that there exist exactly one such function.
Subtasks
 Subtask #1: T = 100; x_{i} ≤ 4 (8 points)
 Subtask #2: T = 1; x_{i} ≤ 5000 (42 points)
 Subtask #3: T = 1; 1 ≤ n ≤ 42 (13 points)
 Subtask #4: T = 1; 1 ≤ n ≤ 100 (17 points)
 Subtask #5: T = 1; original constraints (20 points)
Example
Input: 1 4 3 4 6 10 18 5 6 30 Output: 34 66 73741819
Explanation
Test case 1. The initial 4 numbers Chef has are 1, 2, 0, 1, so, the function f was defined as follows: f(k) = (1^{k} + 2^{k} + 0^{k} + 1^{k}) mod (10^{9} + 7) = (2^{k} + 2) mod (10^{9} + 7).
So, the values given in the input are:
f(1) = (2^{1} + 2) mod (10^{9} + 7) = 4 f(2) = (2^{2} + 2) mod (10^{9} + 7) = 6 f(3) = (2^{3} + 2) mod (10^{9} + 7) = 10 f(4) = (2^{4} + 2) mod (10^{9} + 7) = 18
And the values Chef asked you to calculate are:
f(5) = (2^{5} + 2) mod (10^{9} + 7) = 34 f(6) = (2^{6} + 2) mod (10^{9} + 7) = 66 f(30) = (2^{30} + 2) mod (10^{9} + 7) = 1073741826 mod (10^{9} + 7) = 73741819
Note
You can read about the modulo operation (mod) here: https://en.wikipedia.org/wiki/Modulo_operation.
Author:  alex_2oo8 
Tester:  alex_2oo8 
Editorial  http://discuss.codechef.com/problems/POWSUMS 
Tags  alex_2oo8, dynamicprogramming, matrixexpo, mediumhard, oct16 
Date Added:  11032016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 