Hide

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

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

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

Please log in to submit a solution to this problem

Log in