Candy Distribution

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

WY has n kind of candy, number 1-N, The i-th kind of candy has ai. WY would like to give some of the candy to his teammate Ecry and lasten. To be fair, he hopes that Ecry’s candies are as many as lasten\'s in the end. How many kinds of methods are there?

Input

The first line contains an integer T<=11 which is the number of test cases. 
Then T cases follow. Each case contains two lines. The first line contains one integer n(1<=n<=200). The second line contains n integers ai(1<=ai<=200)

Output

For each test case, output a single integer (the number of ways that WY can distribute candies to his teammates, modulo 109+7 ) in a single line.

Sample Input

2
1
2
2
1 2

Sample Output

2
4

Hint

 

Source

2015 Multi-University Training Contest 1