Finally , all the theory and lab exams of current semester are over and Tarang is going home. At the last night before going home , he has a doubt in his mind. There are n stations between the campus and his home and he can go from ith station to (i + 1)th station by ai roads (1 <= i < n). Here 1st station is same as campus and last(nth) station is same as home.Tarang wants to know the total number of routes through which he can go his home.So he asks the question to his friend Sanjeev. Sanjeev is not in mood of giving any answers , so he sends Tarang to you. Can you give the answer to Tarang's question ? Since the answer may be very large , you have to print the answer modulo (10^12 + 39).

Input

First line contains t (no. of test cases to follow). First line of each test case contains n (no. of stations between campus and home). Next line contains (n - 1) space seperated integers (ith integer ai denotes the number of roads between ith and (i + 1)th station).

Output

Print t lines containing the answer modulo (10^12 + 39).

Constraints

1<= t <= 10
2<= n <= 20
1<= ai <= 10^18

Example

Input:
1
4
3 5 2

Output:
30

Explanation

Let 4 stations are A,B,C,D. There are 3 roads from A to B , 5 roads from B to C and 2 roads from C to D.
so total number of routes = 3 * 5 * 2 = 30.