题目描述

小 $\varsigma$ 发明了一款游戏，规则如下：

• 一行 $n$ 个格子，每格要么为空，要么有一个方块。
• 初始时：某一格生成一个权值 $1$ 的方块，其出现时间定义为 $1$。
• 小 Y 可以进行若干次操作直到游戏失败或胜利（失败和胜利定义见下），第 $i$ 次操作（向左或右滑动）：
  1. 方块全部向一侧紧贴。
  2. 若相邻两个方块权值相等，则合并成一个权值为这两个方块的权值加 $1$ 的方块（可以证明不会出现连续三个相等的情况），合并生成的方块出现时间为 $2i$，随后所有方块继续向左（或右）堆叠，直到不存在能合并的情况为止。
  3. 在另一端生成一个新的 $1$，出现时间为 $2i+1$。若格子已满，则无法生成新方块，游戏失败。
• 若某次出现 $x$，则立即胜利。

定义两个失败状态 本质相同 当且仅当：

1. 每个格子的权值相同；
2. 所有方块出现时间的相对大小关系相同。

求共有多少种 本质不同的失败状态，答案对 $p$ 取模（不保证 $p$ 为质数）。

输入格式

从文件 game1.in 中输入数据。

本题有多组测试数据。

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

输出格式

输出到文件 game1.out 中。

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

输入输出样例

输入1

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

输出1

8
0
12
34
20

【样例1解释 】

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

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

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

• 不存在任何失败状态，答案为 $0$。

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

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

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

• 答案为 $34$，在模 $71$ 意义下为 $34$。

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

• 答案为 $162$，在模 $71$ 意义下为 $20$。

输入2

10 114514
5 10
1 1
9 10
1 5
4 20
3 17
3 16
11 13
51 76
241 261

输出2

162
0
21708
1
34
8
8
69166
70264
3040

数据范围

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

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