You are given a Vector V and Matrix M. V has n variables V1, V2, ..., Vn. M is lower triangular matrix with n rows numbered from 1 to n. Row i has i − 1 column. You can calculate an infinite matrix R by the following equation. { ∑ (Ri−1,j + Vj j−1 iMj,k ∗ Ri,k)%m k=1 if i > 1 if i=1 Ri,j = The matrix R has n columns and infinite rows. Now consider about a function Sp,a,b,c,d. You can calculate this by the following equation. S = p,a,b,c,d (i + 1)p ∗ R %m i+a,j +b ∑c ∑d i=0 j=0 For our problem the value of m is 1000000007. This is a prime number. Your task is to given V and M you have to calculate Sp,a,b,c,d. Input First line contains T (1 ≤ T ≤ 5) the number of test cases. Each test case contains multiple number of lines. Line 1 contains 1 integer n (1 ≤ n ≤ 200). Line 2 to Line n + 1 contains the information about V and M. Among these lines Line i + 1 contains i integers. First integer is the value of Vi (1 ≤ Vi ≤ 200). Subsequent integers are M1,i, M2,i, M3,i, ..., Mi−1,i in order. (0 ≤ Mi,j < min(10, j − i)). Line n + 2 contains an integer q (1 ≤ q ≤ 1000) the number of queries. Each of the next q lines contains 5 integers p (0 ≤ p ≤ 9), a (1 ≤ a ≤ 1015), b (1 ≤ b ≤ n), c (0 ≤ c ≤ 1015), d (0 ≤ d ≤ n − b) separated by a single space. Output For each query output a single integer denoting the value Sp,a,b,c,d. Output a blank lines after each test case. Sample Input 2 4 1 20 310 4210 4 01153 02252 1 2 2 10 2 1 2 3 10 1
2/2 4 1 20 310 4210 4 01153 02252 1 2 2 10 2 1 2 3 10 1 Sample Output 910 1468 79156 78518 910 1468 79156 78518