Polynomial Partition Function

All submissions for this problem are available.
Chef Ciel is participating in an arithmetic contest now.
Why?
Because of the top prize for the contest, a limited edition kitchen knife.
But to win the contest she must calculate the values f(M, N, X) of the function named polynomial partition function.
The polynomial partition function f(M, N, X) is defined by
where P is a given polynomial P(x) = C_{D} · x^{D} + C_{D1} · x^{D1} + ... + C_{1} · x + C_{0}.
For example,
f(1, 3, X) = P(3X)
f(2, 3, X) = P(0) P(3X) + P(X) P(2X) + P(2X) P(X) + P(3X) P(0) = 2 P(X) P(2X) + 2 P(0) P(3X)
f(3, 1, X) = P(0) P(0) P(X) + P(0) P(X) P(0) + P(X) P(0) P(0) = 3 P(0)^{2} P(X)
Ciel is a great chef. However, she is not very good at arithmetic. So she needs your help to make her win the contest.
For the given values of P, M, N and X, your work is to calculate the value of f(M, N, X).
The answer can be very large, so you should print the answer modulo 1000000007 (10^{9}+7), that is, you need to find the remainder of division of f(M, N, X) by 1000000007 (10^{9}+7).
Input
The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line for each test case has 3 integers M, N and X.
Then the next line has D+2 integers. The first integer denotes D, and the (i+1)th integer denotes C_{i1}.
Output
For each test case, print the value of f(M, N, X) modulo 1000000007 (10^{9}+7).
Constraints
1 ≤ T ≤ 4
1 ≤ M ≤ 400
1 ≤ N ≤ 800
0 ≤ X ≤ 1000000006 (10^{9}+6)
0 ≤ D ≤ 10
0 ≤ C_{i} ≤ 1000000006 (10^{9}+6)
If D ≠ 0, then C_{D} ≠ 0
Sample Input
3 1 3 2 2 0 1 2 2 3 0 1 1 1 3 1 1 3 1 2 3 4
Sample Output
78 4 30
Explanation
In the first case, the polynomial is P(x) = 2 · x^{2} + x.
The answer is P(3X) = P(6) = 2 · 36 + 6 = 78.
Author:  laycurse 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/PARPOLY 
Tags  binomial, dynamicprogramming, june12, laycurse, medium 
Date Added:  2092011 
Time Limit:  1.07531 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, 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. 