200933: [AtCoder]ARC093 F - Dark Horse

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

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

Source/Category

加入题单

上一题 下一题 算法标签：