Description
There are many ways to calculate a value of a polynomial. One of them is Horner’s rule:
Given a polynomial and some parameters x, compute P(x) by Horner’s rule.
Input
First line contains a positive integer t(t<=1000), which indicates the number of test cases in the input. In each case, the first line gives an integer n. The second line contains n+1 integers, which are the coefficients of P(x) arranged from the highest power term to the constant term. The third line gives an integer m , which is the number of parameters. In next m lines, each line contains an integer, which indicate the parameter x.
Note : abs(x) means the absolute value of x.
case 1:
1 <= n <= 10
0 <= coefficient <= 10
1 <= m <= 10
0 <= x <= 10
case 2:
1 <= n <= 100
0 <= coefficient <= 100
1 <= m <= 100
0 <= x <= 100
case 3:
1 <= n <= 100
0 <= coefficient <= 10^6
1 <= m <= 100
0 <= x <= 10^6
case 4:
1 <= n <= 100
abs(coefficient) <= 10^6
1 <= m <= 100
abs(x) <= 10^6
Output
For each case, output the case number like “Case 1:” in a line, each value of m parameters is output in a line and mod 10000007. Please refer to sample output.
Note : -1 % 5 should output 4.