## Chef and Professor solution codechef

Chef’s professor gave him homework to find a permutation of length 2N2N such that each integer from 00 to 2N−12N−1 appears **exactly once** in the permutation and the maximum bitwise XOR of any **even length** subarray is minimized.

Chef wonders how many such permutations are there. Help Chef to find out the number of permutations modulo (109+7)(109+7), satisfying the above conditions and also help him find one such permutation.

### Input Format

- First-line will contain TT, the number of test cases. Then the test cases follow.
- The only line of each test case contains an integer NN.

### Output Format Chef and Professor solution codechef

- For each test case, print two lines of output.
- In the first line, print the number of permutations modulo (109+7)(109+7), for which maximum bitwise xor of any even-length subarray is minimized.
- In the next line, print 2N2N space-separated numbers denoting any such permutation.

### Constraints

Also see-

Gates to Another World solution codeforces

### Chef and Professor solution codechef

- 1≤T≤181≤T≤18
- 1≤N≤181≤N≤18
- Sum of 2N2N over all test cases does not exceed 106106

### Sample Input 1

### Chef and Professor solution codechef

```
2
1
2
```

### Sample Output 1

```
2
0 1
8
3 2 0 1
```

### Explanation

### Chef and Professor solution codechef

**Test case 11:** There are two optimal permutations: [0,1][0,1] and [1,0][1,0].

**Test case 22:** The maximum xor value of any even-sized subarray will be 22 and there are 88 such permutations.

Pingback: Amazon Quiz Answers today 31 August 2021- 100% correct answers – Hindimaintutorial

Pingback: Amazon Quiz Answers today 1 September 2021- 100% correct answers – Hindimaintutorial

Pingback: Magical Flips solution codechef – Hindimaintutorial