题目描述
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
输入格式
见题面
输出格式
见题面