题目描述

Suppose you are given two integers, $m$ and $n$. You are also given a list of $n$ distinct integers $x_1, x_2, \dots, x_n$, with $0 \leq x_i \leq 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-$XOR$ with $y$. That is, $y \oplus x_{p_y} > y \oplus x_i$ for all $i = 1..n$, $i \ne p_y$ ($\oplus$ means bitwise-$XOR$).

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

3 6
1
1
2
2
3
4
5
6

4

2 3
1
2
1
3

0

3 8
1
2
3
4
5
6
7
8

1