分数: 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}.
- 重复以下操作,直到该行中只剩下一名玩家:
- 进行以下比赛:行中的第一个玩家对行中的第二个玩家,第三个玩家对第四个玩家,依此类推。输了的玩家离开队伍。获胜的玩家再次站成一排,保持玩家的相对顺序。
- 排在最后的玩家就是冠军。
已知,两个玩家之间的比赛结果可以写成如下,使用 M 整数 A_1, A_2, ..., A_M 作为输入给出:
- 当 y = A_i 对于一些 i,玩家之间比赛的获胜者 1 和玩家 y (2 \leq y \leq 2^N) 将成为玩家 y.
- 当 y \neq A_i 对于每个 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