November 30, 2023
Latest:
CodeChef Solution

# Parity Permutation CodeChef Solution ## Problem

You are given an array  of length  containing distinct integers and an integer  (either 0 or 1).

Your task is to find the total number of permutations of array  such that for all pairs (�,�) with 1≤�<�≤�, and (�+�) being an odd number:

• (��+��)%2 =�

You should output the count of such permutations modulo 109+7.

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers  and , as mentioned in statement.
• The second line of each test case contains  space-separated integers �1,�2,…,�� — the elements of the array.

### Output Format

For each test case, output on a new line, the total number of permutations of array  satisfying the conditions, modulo 109+7.

### Constraints

• 1≤�≤105
• 1≤�≤105
• 1≤��≤109
• 0≤�≤1
• The sum of  over all test cases won’t exceed 5⋅105.

### Sample 1:

Input

Output

3
5 0
6 10 1 4 8
4 0
17 13 21 3
3 1
1 2 3

0
24
2

### Explanation:

Test Case 1: There is no permutation that satisfies the required conditions.

Test Case 2: All the permutations of the array satisfy the required conditions.

Test Case 3: Two permutations satisfy the conditions. They are:

• [1,2,3]: The pairs under consideration are (1,2) and (2,3). Here (�1+�2)%2=1=�. Similarly (�2+�3)%2=1=�.
• [3,2,1] The pairs under consideration are (1,2) and (2,3). Here (�1+�2)%2=1=�. Similarly (�2+�3)%2=1=�. 