2048（game）

题目背景

注意：本场比赛提交时不开启文件输入输出。

---

《2048》是一款非常好玩，火爆全球的小游戏。

题目描述

现在，小 Y 把《2048》稍做修改，得到如下的一维变种（其中部分规则可能与你对《2048》的印象相悖，请以下文为准）：

• 游戏在一行 $n$ 个格子组成的网格中进行。每个格子要么为空，要么包含一个带有正整数权值的方块。
• 游戏开始时，会在一个任意的格子上生成一个权值为 $2$ 的方块，其他格子为空。
• 玩家通过向左（或右，下同）滑动进行操作。每次操作：
  1. 所有方块将全部靠左（或右）堆叠放置，彼此紧贴，不留空位。
  2. 如果堆叠完毕后，存在相邻的两个方块权值相等，设其权值均为 $k$，则消除这两个方块，并在原先其中一个方块的位置生成一个权值为 $2k$ 的方块（这称作一次合并）（可以证明，在该游戏过程中不会存在连续 $\bm 3$ 个相邻方块权值相等，因此不需要考虑合并顺序的问题），随后所有方块继续向左（或右）堆叠，直到不存在能合并的情况为止。
  3. 最后，在最右（或左）端，即滑动方向的相反方向，生成一个权值为 $2$ 的新方块。

下图展示了一次向左滑动操作的示例。

• 称一个方块的出现时间是它被生成时，游戏进行的轮数，即玩家进行滑动操作的次数。
• 游戏的目标是生成 $2^x$，因此在游戏的任何过程中，一旦出现了 $2^x$，游戏立刻结束，且游戏胜利。
• 如果一次滑动操作的步骤 2 结束时，所有 $n$ 个格子全都包含方块（事实上，这次滑动操作是滑不动的，但仍然认为是一次滑动操作），则步骤 3 中无法正常生成新方块，不会进行步骤 3，且游戏失败。

小 Y 正在研究这个新 2048 游戏的所有失败状态的个数。具体地，在游戏失败时，两个失败状态 A 和 B 被认为本质相同，当且仅当以下条件同时成立：

• 对每个 $1 \leq i \leq n$，A 中方块 $i$ 和 B 中方块 $i$ 的权值均相同；
• 对每对 $1 \le i < j \le n$，A 中的方块 $i$ 与方块 $j$ 的出现时间的大小关系，与 B 中的方块 $i$ 与方块 $j$ 的出现时间的大小关系相同。这里大小关系指的是大于、小于、或等于。

小 Y 想要知道，总共有多少种本质不同的失败状态。答案对给定模数 $p$ 取模（$p$ 未必为素数）。

输入格式

本题有多组测试数据。

第一行，两个正整数 $T, p$，分别表示数据组数和模数。对于每组数据：

• 仅一行，两个整数 $n, x$。

输出格式

对于每组数据：

• 仅一行一个正整数，表示本质不同的失败状态数，答案对 $p$ 取模。

样例 #1

样例输入 #1

5 71
3 4
4 3
4 4
4 5
5 6

样例输出 #1

8
0
10
32
4

提示

【样例解释 #1】

对于第一组数据，$n = 3$，$x = 4$：

• 仅从网格状态上看，共有 $6$ 种失败的可能性：$[8, 4, 2], [2, 4, 8], [2, 8, 4], [4, 8, 2], [2, 8, 2],[2, 4, 2]$。
  • 但考虑 $[2, 8, 2]$，其可以对应两种本质不同的失败状态：
    • 中间的 $8$ 先被生成，随后左边的 $2$ 出现，随后右边的 $2$ 出现；
    • 中间的 $8$ 先被生成，随后右边的 $2$ 出现，随后左边的 $2$ 出现。
  • 对于 $[2, 4, 2]$ 也是同理。
• 对于其它的可能性，可以证明其只能对应一种本质不同的失败状态。
• 所以，答案为 $1 + 1 + 1 + 1 + 2 + 2 = 8$，在模 $71$ 意义下为 $8$。

对于第二组数据，$n = 4$，$x = 3$：

• 可以证明，无论如何，游戏都将胜利，因此不存在任何失败状态，答案为 $0$。

对于第三组数据，$n = 4$，$x = 4$：

• 仅从网格状态上看，共有 $4$ 种失败的可能性：$[2, 8, 4, 2], [2, 4, 8, 2], [4, 8, 4, 2],[2, 4, 8, 4]$。
• 其中，$[2, 8, 4, 2]$ 和 $[2, 4, 8, 2]$ 分别对应 $3$ 种本质不同的失败情况，$[4,8,4,2]$ 和 $[2, 4, 8, 4]$ 分别对应 $2$ 种本质不同的失败情况。故答案为 $3 + 3 + 2 + 2 = 10$，在模 $71$ 意义下为 $10$。

对于第四组数据，$n = 4$，$x = 5$：

• 可以证明答案为 $32$，在模 $71$ 意义下为 $32$。

对于第五组数据，$n = 5$，$x = 6$：

• 可以证明答案为 $146$，在模 $71$ 意义下为 $4$。

【样例 #2】

见附件中的 game/game2.in 与 game/game2.ans。

该组样例满足测试点 $3 \sim 5$ 的约束条件。

【样例 #3】

见附件中的 game/game3.in 与 game/game3.ans。

该组样例满足测试点 $6 \sim 10$ 的约束条件。

【样例 #4】

见附件中的 game/game4.in 与 game/game4.ans。

该组样例满足测试点 $14 \sim 17$ 的约束条件。

【样例 #5】

见附件中的 game/game5.in 与 game/game5.ans。

该组样例满足测试点 $22 \sim 25$ 的约束条件。

【数据范围】

本题共 $25$ 个测试点，每个 $4$ 分。

测试点编号	$T \le$	$n,x \le$	特殊性质
$1\sim2$	$10$	$4$	无
$3\sim5$		$10$
$6\sim10$		$22$
$11\sim13$	$1$	$80$
$14\sim17$	$1000$
$18\sim20$	$1$	$300$
$21$	$10^5$		$p = 2$
$22\sim25$			无

对于全部数据，保证：$1\le T\le 10^5$，$1\le n,x\le 300$，$2\le p\le10^9$。

样例下载