I

Infinite Matrix Input: Standard Input Output: Standard Output

You are given a Vector V and Matrix M. V has n variables V₁,V₂,….,V_n. 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.

The matrix R has n columns and infinite rows. Now consider about a function S_p,a,b,c,d.

You can calculate this by the following equation.

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 S_p,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 ingers.

First integer is the value of V_i(1≤ V_i ≤200). Subsequent integers are M_1,i, M_2,i, M_3,i, …. , M_i-1,i in order. (0≤M_i,j <minimum(10,j-i)).

Line n+2 contains an integer q(1≤q≤1000) the number of queries. Each of the next q line contains 5 integers p(0≤p≤9),a(1≤a≤10¹⁵),b(1≤b≤n),c(0≤c≤10¹⁵),d(0≤d≤n-b) separated by a single space.

Output

For each query output a single integer denoting the value S_p,a,b,c,d. Output a blank lines after each test case.

Sample Input Output for Sample Input

2 4 1 2 0 3 1 0 4 2 1 0 4 0 1 1 5 3 0 2 2 5 2 1 2 2 10 2 1 2 3 10 1 4 1 2 0 3 1 0 4 2 1 0 4 0 1 1 5 3 0 2 2 5 2 1 2 2 10 2 1 2 3 10 1

910 1468 79156 78518 910 1468 79156 78518

---

Problem setter: Abdullah al Mahmud, Special Thanks: Derek Kisman, Manzurur Rahman Khan