p-and-his-chocolates

A boy named P loves a girl named G. It is the Valentine's week and Chocolate Day is approaching, so P wants to give some chocolates to G but he is afraid to give them himself. So he takes help of another girl named S.

P buys some chocolates from a shop. There are N types of chocolates and there are a total of Ai chocolates of ith type where 1 ≤ i ≤ N. 

Now P gives these chocolates to S and tells her to give them to G for him. However S likes chocolates so much that she eats all the chocolates and tells P that 
G refused his chocolates.

Now, S has a very peculiar way of eating the chocolates. She eats the last chocolate of type i +1 only after she has finished eating all chocolates of 
type i (for all 1 ≤ i < N).

Given all the values of Ai, you need to find the number of ways S can eat those chocolates. 

Chocolates of same type should be considered non distinguishable. 

INPUT:

First line of input contains an integer T (1≤ T ≤ 10), the number of test cases. 

First line of each test case contains an integer N (1≤ N ≤ 1027). Next line of each test case contains N integers. 
The ith integer corresponds to the value ai. (1 ≤ Ai ≤ 1027).
Also, total number of chocolates is less than or equal to 1027.

OUTPUT:

For each test case print a single integer, the number of ways S can eat those chocolates. As the number can be very large, print it modulo 10^9+7.

SAMPLE INPUT
2
1
5
3
3 2 1

SAMPLE OUTPUT
1
4

Explanation

1st Test Case

There are 5 chocolates of Type 1. So, S has only one way of eating them.

2nd Test Case

Here, There are 3 chocolates of Type 1, 2 chocolates of Type 2 and 1 chocolate of Type 3. S can eat them in the following 4 ways:
1 1 1 2 2 3
1 1 2 1 2 3
1 2 1 1 2 3
2 1 1 1 2 3

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: