← 返回题目列表

AtCoder · arc093_d

F. 黑马

中文机器翻译题面 查看原题

分数: 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