Suppose you are given two integers, $m$ and $n$. You are also given a list of $n$ distinct integers $x_1, x_2, \ldots , x_ n$, with $0\! \le \! x_ i\! \le \! 2^m{-}1$. For each number $y$ from $0$ to $2^m{-}1$, you’ve found the number $p_ y$ such that $x_{p_ y}$ has a maximum bitwise-$\operatorname {XOR}$ with $y$. That is, $y\! \oplus \! x_{p_ y}\! >\! y\! \oplus \! x_ i$ for all $i\! =\! 1..n, i\! \neq \! p_ y$ ($\oplus $ means bitwise-$\operatorname {XOR}$).

Now, consider the reverse problem. Given $m$, $n$, and the sequence $p_0, p_1, \ldots , p_{2^m{-}1}$, count the number of sequences of distinct integers $x_1, x_2, \ldots , x_ n$ that could have generated that $p$ sequence from the above algorithm. Two $x$ sequences are different if there is some $i$ such that $x_ i$ in one sequence is different from $x_ i$ in the other sequence. Output this count modulo $10^9{+}7$.

-----Input-----
Each test case will begin with a line with two space-separated integers $m$ ($0\! \le \! m\! \le \! 16$) and $n$ ($1\! \le \! n\! \le \! 2^m$), where $2^m$ is the length of the $p$ sequence, and $n$ is the length of the $x$ sequences.

Each of the next $2^m$ lines will contain a single integer $p$ ($1\! \le \! p\! \le \! n$). These are the values of the sequence $p_0, p_1, \ldots , p_{2^m{-}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 $x_1, x_2, \ldots , x_ n$ which could have generated the sequence $p_0, p_1, \ldots , p_{2^m{-}1}$ from the above algorithm, modulo $10^9{+}7$.

-----Examples-----
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

Source: kattis | Difficulty: MEDIUM


Solutions: