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.