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, both of which go to final and become champion and runner-up. They have such a 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, they say, “the ranking is a lie; no ranking system can judge VOID.” All of the members have to have a nickname 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 the others' names because they have only one-word names. He thinks that names should consist of many words like VOID IAmLegend, VOID LoveIsADangerousDisadvantage, etc. Now he wants to change the names of all the members according to this rule. But the members are not very good at giving long names. So he decides to make some lists of cool words and make all members choose a name in the following way.

There are N lists of words. The i-th list contains W_i words (1 ≤ i ≤ N). All words will be distinct. The rules are the following:

1. A member can only choose zero or one word from each list.
2. A member will choose words from the lists in sequence, beginning with list 1 and finishing with list N.
3. The names must consist of at least 2 words.

For example, here are three lists of words:

List 1	List 2	List 3
Call	Of	Duty
Age		Empires

Here, W₁ = 2, W₂ = 1, W₃ = 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 described way. Since this can be a big number, give the result modulo 1 000 000 007.

Input Specification

The first line of the 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 W_i (1 ≤ W_i ≤ 10⁹).

Output Specification

For each test case, output exactly one line containing a single integer, the number of names that can be formed modulo 1 000 000 007.

Sample Input

1. 3
2. 3
3. 2 1 2
4. 3
5. 2 2 2
6. 3
7. 3 2 3

download as text file

Output for Sample Input

1. 12
2. 20
3. 39

download as text file