All of you who are related to gaming know the name of Call Of Duty Legends of Bangladesh. Yes, I am talking about VOID. They are so pro that they have two teams and both of the teams go to final and become champion and runner up. They have such strong brotherhood that sometimes they toss the coin to decide who will be the champion. Although, They are now ranked 9th among all the teams, but they say,“the ranking is a lie. No ranking system can judge VOID ”. All of the members have to have a nick name for VOID. Current members are VOID LeapOfFaith, VOID wrath, VOID kopal, VOID aragorn, and VOID faltu. Now their leader is VOID LeapOfFaith. He does not like others names because they have only one word name. He thinks that names should be consists of many words like VOID IAmLegend, VOID LoveIsADangerousDisadvantage etc. Now he wants to change name of all the members according to new rule. But the members are not very good at giving long names. So he decides to make some list of cool words and make the entire member to choose name in following way. There are N lists of word. i-th list have Wi (1 ≤ i ≤ N) number of word. All the words will be distinct. Rules are:
2/2 Input First line of input will contain the number of test cases, T ≤ 20. Each test case is described by exactly two lines. The first line contains an integer N (2 ≤ N ≤ 5000). The second line contains N space-separated integers Wi (1 ≤ Wi ≤ 109). Output For each test case output exactly one line containing a single integer, how many names can be formed modulo 1000000007. Sample Input 3 3 212 3 222 3 323 Sample Output 12 20 39