The Election of Noakhali

OnikJahanSagor Criterion 2022 Round 17
Limits 1s, 512 MB

Recently, Noakhali became a sovereign state. As a result, the first parliamentary election of the Republic of Noakhali is going to be held soon.

Sajid is a polling officer at an election center. There will be exactly NN queues of voters and Sajid knows exactly how many voters will be in each queue. At a time, only one person from the front of a non-empty queue will come and give their votes. After that, they will be headed home. The order of persons in each queue is known beforehand. As it’s the first election of their newborn nation, Sajid wants to know every possible situation and be prepared for them. As part of that, he wants to know in how many ways voters can give their votes.

Two ways are said to be different if the sequence of voters giving votes is different.

Input

First line of input will contain an integer TT (1T1061\leq T \leq 10^{6}), the number of test cases.

Next 2×T2\times T lines will describe the test cases.

First line of each test case will contain an integer N(1N106)N(1 \leq N \leq 10^{6}), the number of queues.

Second line of each test case will contain NN space separated integers A1,A2,A3,,AN ( 0Ai106 )A_{1}, A_{2}, A_{3},\dots,A_{N} ~(~0 \leq A_{i} \leq 10^{6}~), where AiA_{i} is the number of voters in ii-th queue.

The sum of NN over all test cases does not exceed 10610^{6}.

The sum of the voters of the queues of a single test case does not exceed 10610^{6}.

Output

For each test cases, print the answer on a separate line.

As the answer can be really big, print it modulo 109+710^{9} + 7.

Sample

InputOutput
1
2
2 1
3

There are 33 ways to take the votes described below,

The first vote from the first queue, the second vote from the first queue and the third vote from the second queue.

The first vote from the first queue, the second vote from the second queue and the third vote from the first queue.

The first vote from the second queue, the second vote from the first queue and the third vote from the first queue.


Submit

Login to submit.

Statistics

50% Solution Ratio
NirjhorEarliest, 1M ago
AlfehsaniFastest, 0.1s
Sohel_RanaLightest, 9.0 MB
serotoninShortest, 724B
Toph uses cookies. By continuing you agree to our Cookie Policy.