Chef and Functions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has just been introduced to functions and he has been experimenting a lot with the different kinds of functions. In the process, the chef has come up with an interesting problem for you.
Chef defines a function root(i, x) which gives the greatest integer less than or equal to the i ^{th} root of a positive integer x . For example, root(2, 4) is 2 and root(2, 2) is 1 .
Now the chef defines another function val(x, A, N) as follows :
val(x, A, N) = root(1, x)*A[1] + root(2, x)*A[2] + ... + root(N, x)*A[N]
where A is an array of integers of size N (indexed from 1 onwards) and x is a positive integer.
You are given the array A and its size N . You need to find out the value of val(x, A, N) for several values of x . Since this number can be very large, print the result modulo 10^{9} + 7 .
Input
The first line contains an integer T denoting the number of test cases. Each test case begins with a line containing two integers N and Q denoting the size of array A and the number of queries. The second line of each test case consists of N space separated integers where the i^{th} integer represents A[i]. The third line of each test case consists of Q space separated integers denoting the value of x for the i^{th} query.
Output
For each test case, print in a single line Q integers, where the i^{th} integer represents the answer to the i^{th} query. ( i.e val(x, A, N) % ( 10^{9} + 7 ) )
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{4}
 1 ≤ Q ≤ 15000
 10^{9} ≤ A[i] ≤ 10^{9}
 1 ≤ x ≤ 10^{18} for each number in the query.
Example
Input: 1 3 2 4 5 6 8 30
Output: 54 163
Explanation
Query 1.
(root(1,8)*4 + root(2,8)*5 + root(3,8)*6) % 1000000007 = (8*4 + 2*5 + 2*6) % 1000000007 = 54 % 1000000007 = 54
Query 2.
(root(1,30)*4 + root(2,30)*5 + root(3,30)*6) % 1000000007 = (30*4 + 5*5 + 3*6) % 1000000007 = 163 % 1000000007 = 163
Author:  viv001 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/FUNC 
Tags  binarysearch, june14, medium, numbertheory, viv001 
Date Added:  8012014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, 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.5, 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
HELP
If you are still having problems, see a sample solution here. 