VOID 

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$ \le$i$ \le$N) number of word. All the words will be distinct. Rules are:

  1. A member can only choose one word from one list or not choose from that list.
  2. A member will choose serially beginning from list 1 to N.
  3. The name must be consisting of at least 2 words.

Like there are three lists of word.

List1 List2 List3
Call Of Duty
Age Empires

Here, W1 = 2, W2 = 1, W3 = 2.

There are 12 possible names :

  1. Call Of Duty
  2. Call Of
  3. Call Duty
  4. Call Of Empires
  5. Call Empires
  6. Age Of Duty
  7. Age Of
  8. Age Duty
  9. Age Of Empires
  10. Age Empires
  11. Of Duty
  12. Of Empires

Now, you are given the number of words in the lists. You have to determine how many names can be formed in the previous way. Since that can be a big number give that modulo 1000000007.

Input 

First line of input will contain the number of test cases, T$ \le$20. Each test case is described by exactly two lines. The first line contains an integer N ( 2$ \le$N$ \le$5000). The second line contains N space-separated integers Wi ( 1$ \le$Wi$ \le$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
2 1 2
3
2 2 2
3
3 2 3

Sample Output  

12
20
39


Problem Setter: F. A.Rezaur Rahman Chowdhury
Special Thanks: Prasanjit Barua Linkin