XOR Sequences

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$.

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 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$.

Sample Input 1 | Sample Output 1 |
---|---|

3 6 1 1 2 2 3 4 5 6 |
4 |

Sample Input 2 | Sample Output 2 |
---|---|

2 3 1 2 1 3 |
0 |

Sample Input 3 | Sample Output 3 |
---|---|

3 8 1 2 3 4 5 6 7 8 |
1 |