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.