配点 : $1100$ 点

問題文

$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$ 番目、$...$ の選手が対戦を行う。 負けた選手は列から離れる。勝った選手たちは相対順序を保ったまま改めて一列に並ぶ。
• 列の前から $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$ で割ったあまりを求めてください。

制約

• $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$)

入力

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

$N$ $M$

$A_1$ $A_2$ $...$ $A_M$

出力

答えを出力せよ。

2 1
3

8

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

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