#P10910. [2015杭电多校]Candy Distribution

    ID: 10052 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF2100提高计数 DP普通生成函数生成函数求系数前缀和优化 DP滚动数组偏移索引

[2015杭电多校]Candy Distribution

Candy Distribution

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 TT 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 10 9 +7 ) in a single line.

Sample Input

2
1
2
2
1 2

Sample Output

2
4

Hint

Sample: a total of 4, (1) Ecry and lasten are not assigned to the candy; (2) Ecry and lasten each to a second kind of candy; (3) Ecry points to one of the first kind of candy, lasten points to a second type of candy; (4) Ecry points to a second type of candy, lasten points to one of the first kind of candy.

Author

FZUACM

Source

2015 Multi-University Training Contest 1