/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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 番目、... の選手が対戦を行う。 負けた選手は列から離れる。勝った選手たちは相対順序を保ったまま改めて一列に並ぶ。
- 最後まで残った選手が優勝である。
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
出力
答えを出力せよ。
入力例 1
2 1 3
出力例 1
8
条件を満たす p としては [1, 4, 2, 3] や [3, 2, 1, 4] などが、条件を満たさない p としては [1, 2, 3, 4] や [1, 3, 2, 4] などがあります。
入力例 2
4 3 2 4 6
出力例 2
0
入力例 3
3 0
出力例 3
40320
入力例 4
3 3 3 4 7
出力例 4
2688
入力例 5
16 16 5489 5490 5491 5492 5493 5494 5495 5497 18993 18995 18997 18999 19000 19001 19002 19003
出力例 5
816646464
Score : 1100 points
Problem Statement
There are 2^N players, numbered 1, 2, ..., 2^N. They decided to hold a tournament.
The tournament proceeds as follows:
- Choose a permutation of 1, 2, ..., 2^N: p_1, p_2, ..., p_{2^N}.
- The players stand in a row in the order of Player p_1, Player p_2, ..., Player p_{2^N}.
- Repeat the following until there is only one player remaining in the row:
- Play the following matches: the first player in the row versus the second player in the row, the third player versus the fourth player, and so on. The players who lose leave the row. The players who win stand in a row again, preserving the relative order of the players.
- The last player who remains in the row is the champion.
It is known that, the result of the match between two players can be written as follows, using M integers A_1, A_2, ..., A_M given as input:
- When y = A_i for some i, the winner of the match between Player 1 and Player y (2 \leq y \leq 2^N) will be Player y.
- When y \neq A_i for every i, the winner of the match between Player 1 and Player y (2 \leq y \leq 2^N) will be Player 1.
- When 2 \leq x < y \leq 2^N, the winner of the match between Player x and Player y will be Player x.
The champion of this tournament depends only on the permutation p_1, p_2, ..., p_{2^N} chosen at the beginning. Find the number of permutation p_1, p_2, ..., p_{2^N} chosen at the beginning of the tournament that would result in Player 1 becoming the champion, modulo 10^9 + 7.
Constraints
- 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)
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_M
Output
Print the answer.
Sample Input 1
2 1 3
Sample Output 1
8
Examples of p that satisfy the condition are: [1, 4, 2, 3] and [3, 2, 1, 4]. Examples of p that do not satisfy the condition are: [1, 2, 3, 4] and [1, 3, 2, 4].
Sample Input 2
4 3 2 4 6
Sample Output 2
0
Sample Input 3
3 0
Sample Output 3
40320
Sample Input 4
3 3 3 4 7
Sample Output 4
2688
Sample Input 5
16 16 5489 5490 5491 5492 5493 5494 5495 5497 18993 18995 18997 18999 19000 19001 19002 19003
Sample Output 5
816646464