题目描述

$2^N$ 人の選手がおり、それぞれ $1,\ 2,\ ...,\ 2^N$ の番号がついています。 これらの選手でトーナメントを行うことにしました。

トーナメントは以下のようにして行われます。

• $1,\ 2,\ ...,\ 2^N$ の置換 $p_1,\ p_2,\ ...,\ p_{2^N}$ を選ぶ。
• 選手たちが選手 $p_1$, 選手 $p_2$, $...$, 選手 $p_{2^N}$ の順に一列に並ぶ。
• 列に残っている選手が $1$ 人だけになるまで、以下を繰り返す。
  • 列の前から $1$ 番目と $2$ 番目、$3$ 番目と $4$ 番目、$...$ の選手が対戦を行う。 負けた選手は列から離れる。勝った選手たちは相対順序を保ったまま改めて一列に並ぶ。
• 最後まで残った選手が優勝である。

$2$ 人の選手が対戦したときの結果は、入力として与えられる $M$ 個の 整数 $A_1,\ A_2,\ ...,\ A_M$ を用いて以下のように書けることが分かっています。

• ある $i$ について $y\ =\ A_i$ のとき、選手 $1$ と選手 $y$ ($2\ \leq\ y\ \leq\ 2^N$) が対戦すると選手 $y$ が勝つ。
• どの $i$ についても $y\ \neq\ A_i$ のとき、選手 $1$ と選手 $y$ ($2\ \leq\ y\ \leq\ 2^N$) が対戦すると選手 $1$ が勝つ。
• $2\ \leq\ x\ <\ y\ \leq\ 2^N$ のとき、選手 $x$ と選手 $y$ が対戦すると選手 $x$ が勝つ。

このトーナメントの優勝者は、最初に選ぶ置換 $p_1,\ p_2,\ ...,\ p_{2^N}$ だけに依存します。 トーナメントを行う際に最初に選ぶ置換 $p_1,\ p_2,\ ...,\ p_{2^N}$ であって、 トーナメントの結果選手 $1$ が優勝するようなものの個数を $10^9\ +\ 7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $...$ $A_M$

输出格式

答えを出力せよ。

题目大意

【题意简述】

• 有 $2^N$ 个人，按照满二叉树的形态进行淘汰赛，一开始的排列顺序为所有 $(2^N)!$ 个排列之一。
• 你是第 $1$ 个人，已知每一对人之间的实力关系，具体地说：
  • 给出 $M$ 个人 $A_1 \sim A_M$。
  • 这 $M$ 个人都打得过你。
  • 你打得过除了这 $M$ 个人之外的所有其他人。
  • 对于剩下的情况（你不参与的情况），编号小的人胜利。
• 问你在所有的 $(2^N)!$ 种情况中，有多少种情况可以取得最终胜利。答案对 ${10}^9 + 7$ 取模。

【输入格式】

第一行两个整数 $N, M$。
第二行 $M$ 个整数 $A_1, A_2, \ldots , A_M$。

【输出格式】

输出一个数表示方案数，对 ${10}^9 + 7$ 取模。

【数据范围】

$1 \le N \le 16$，$0 \le M \le 16$，$2 \le A_i \le 2^N$，$A_i < A_{i + 1}$。

2 1
3

8

4 3
2 4 6

0

3 0

40320

3 3
3 4 7

2688

16 16
5489 5490 5491 5492 5493 5494 5495 5497 18993 18995 18997 18999 19000 19001 19002 19003

816646464

提示

制約

• $1\ \leq\ N\ \leq\ 16$
• $0\ \leq\ M\ \leq\ 16$
• $2\ \leq\ A_i\ \leq\ 2^N$ ($1\ \leq\ i\ \leq\ M$)
• $A_i\ <\ A_{i\ +\ 1}$ ($1\ \leq\ i\ <\ M$)

Sample Explanation 1

条件を満たす $p$ としては $[1,\ 4,\ 2,\ 3]$ や $[3,\ 2,\ 1,\ 4]$ などが、条件を満たさない $p$ としては $[1,\ 2,\ 3,\ 4]$ や $[1,\ 3,\ 2,\ 4]$ などがあります。