Problem Description
Suppose you are given two integers, m and n. You are also given a list of n distinct integers x1,x2,⋯,xn, with 0≤xi≤2m−1. For each number y from 0 to 2m−1, you've found the number py such that xpy has a maximum bitwise-XOR with y. That is, y⊕xpy>y⊕xi for all i=1⋯n,i≠py(⊕ means bitwise-XOR).
Now, consider the reverse problem. Given m,n, and the sequence p0,p1,⋯,p2m−1, count the number of sequences of distinct integers x1,x2,⋯,xn that could have generated that p sequence from the above algorithm. Two x sequences are different if there is some i such that xi in one sequence is different from xi in the other sequence. Output this count modulo 109+7.
Input
Each test case will begin with a line with two space-separated integers m (0≤m≤16) and n(1≤n≤2m), where 2m is the length of the p sequence, and n is the length of the x sequences.
Each of the next 2m lines will contain a single integer p (1≤p≤n). These are the values of the sequence p0,p1,...,p2m−1, in order. Every value from 1 to n inclusive will appear at least once.
Output
Output a single integer, which is the number of sequences x1,x−2,⋯,xn which could have generated the sequence p0,p1,⋯,p2m−1 from the above algorithm, modulo 109+7.
Samples
Sample Input 1
3 6
1
1
2
2
3
4
5
6
Sample Output 1
4
Sample Input 2
2 3
1
2
1
3
Sample Output 2
0
Sample Input 3
3 8
1
2
3
4
5
6
7
8
Sample Output 3
1