Chef's professor gave him homework to find a permutation of length 2^{N} such that each integer from 0 to 2^{N}  - 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 (10^{9} + 7), satisfying the above conditions and also help him find one such permutation.

------ Input Format ------ 

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

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 18$
$1 ≤ N ≤ 18$
- Sum of $2^{N}$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
1
2

----- Sample Output 1 ------ 
2
0 1
8
3 2 0 1

----- explanation 1 ------ 
Test case $1$: There are two optimal permutations: $[0,1]$ and $[1,0]$.

Test case $2$: The maximum xor value of any even-sized subarray will be $2$ and there are $8$ such permutations.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
mod = 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
		print(0, 1)
	else:
		n = 1 << n
		ans = 4
		for i in range(1, int(n / 2) + 1):
			ans = ans * i % mod
		print(ans)
		print(0, end=' ')
		for i in range(1, int(n / 2)):
			if i & 1:
				print(i, n >> 1 ^ i, end=' ')
			else:
				print(n >> 1 ^ i, i, end=' ')
		print(n >> 1)


f = []
for i in range(0, 3 * 10 ** 5):
	f.append(0)
mod = 10 ** 9 + 7
f[0] = 1
for i in range(1, 3 * 10 ** 5):
	f[i] = i * f[i - 1] % mod
t = int(input())
while t:
	t -= 1
	n = int(input())
	n = 1 << n
	if n == 2:
		print(2)
	else:
		print(4 * f[n // 2] % mod)
	for j in range(n // 2):
		if j & 1:
			print(j, j + n // 2, end=' ')
		else:
			print(j + n // 2, j, end=' ')
	print('\n')