QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#3013. XOR Sequences

Statistics

Problem Description

Suppose you are given two integers, $m$ and $n$. You are also given a list of $n$ distinct integers $x_1, x_2, \cdots , x_n$, with $0 \leq x_i \leq 2m−1$. For each number $y$ from $0$ to $2m−1$, you've found the number $p_y$ such that $x_{p_y}$ has a maximum bitwise-$\text{XOR}$ with $y$. That is, $y \oplus x_{p_y} > y \oplus x_i$ for all $i = 1 \cdots n, i \ne py$($\oplus$ means bitwise-$\text{XOR}$).

Now, consider the reverse problem. Given $m, n$, and the sequence $p_0, p_1, \cdots , p_{2m−1}$, count the number of sequences of distinct integers $x_1, x_2, \cdots , 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 \leq m \leq 16$) and $n$($1 \leq n \leq 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 \leq p \leq n$). These are the values of the sequence $p_0, p_1, . . . , p_{2m−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, \cdots , x_n$ which could have generated the sequence $p_0, p_1, \cdots , p_{2m−1}$ from the above algorithm, modulo $10^9+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