We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- All Contests
- HourRank 29
- Array Partition
Array Partition
Array Partition
Given an array consisting of positive integers, split the array into non empty subsets and such that an element from array either belongs to subset or to subset and . Calculate the number of ways of splitting the array into 2 subsets and .
Since the answer can be quite large, print it modulo .
Input Format
First line of input contains a single integer denoting number of test cases.
First line of each test case contains a single integer denoting size of array .
Second line of each test case contains space separated integer denoting elements of array .
Constraints
Scoring
- for test data.
- for test data.
- for test data.
Output Format
Output consists of lines, where lines contains required answer for test cases.
Sample Input 0
3
3
2 3 1
3
2 3 6
4
2 3 6 1
Sample Output 0
6
0
2
Explanation 0
- For test case, following paritions are possible
- {1}, {2, 3} = = 1
- {1, 2}, {3} = = 1
- {1, 3}, {2} = = 1
- {2, 3}, {1} = = 1
- {3}, {1, 2} = = 1
- {2}, {1, 3} = = 1
- For test case, any partition will not result = 1.