[ARC093F] Dark Horse

**【题意简述】** - 有 $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}$。

[problemUrl]: https://atcoder.jp/contests/arc093/tasks/arc093_d $ 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 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] $ などがあります。