Background

Original link: https://oier.team/problems/J8D.

2048 is a very fun mini game that is popular worldwide.

Problem Description

Now, Little Y has made a small modification to 2048, obtaining the following one-dimensional variant (some rules may differ from what you remember about 2048; please follow the rules below):

• The game is played on a grid consisting of $n$ cells in a single row. Each cell is either empty or contains a tile with a positive integer value.
• At the beginning of the game, a tile with value $2$ is generated in an arbitrary cell, and all other cells are empty.
• The player operates by sliding left (or right; similarly below). In each operation:
  1. All tiles are stacked completely to the left (or right), placed tightly with no empty cells in between.
  2. If after stacking there exist two adjacent tiles with equal values, suppose both values are $k$, then remove these two tiles and generate a new tile with value $2k$ at the position of one of the original tiles (this is called a merge) (it can be proven that during this game there will never be $\bm 3$ consecutive adjacent tiles with the same value, so you do not need to consider the merge order). Then all tiles continue to stack to the left (or right) until no further merges are possible.
  3. Finally, generate a new tile with value $2$ at the far right (or far left), i.e., the direction opposite to the sliding direction.

The figure below shows an example of a left slide operation.

• Define the appearance time of a tile as follows:
  • Suppose when it is generated, the game is in round $i$ (i.e., the number of slide operations the player has performed), including the current operation.
  • If this tile is generated by merging, its appearance time is defined as $2 i$.
  • Otherwise, if this tile is newly generated, its appearance time is defined as $2 i + 1$.
  • If this tile is the initial tile with value $2$ generated at the very beginning of the game, its appearance time is defined as $1$.
  • It can be proven that with the appearance time defined above, at any moment during the game, any two different tiles have different appearance times.
• The goal of the game is to generate $2^x$. Therefore, at any time during the game, once $2^x$ appears, the game ends immediately and the player wins.
• If after step 2 of a slide operation, all $n$ cells contain tiles (in fact, the slide cannot move anything, but it is still considered an operation), then in step 3 a new tile cannot be generated normally; step 3 will not be performed, and the game fails.

Little Y is studying the number of all failure states in this new 2048 game. Specifically, when the game fails, two failure states A and B are considered essentially the same if and only if the following conditions are both satisfied:

• For every $1 \leq i \leq n$, the values of tile $i$ in A and tile $i$ in B are the same.
• For every pair $1 \le i < j \le n$, the order relation between the appearance times of tile $i$ and tile $j$ in A is the same as that in B.

Little Y wants to know how many essentially different failure states there are in total. The answer should be taken modulo the given modulus $p$ ($p$ is not necessarily prime).

Input Format

This problem contains multiple test cases.

The first line contains two positive integers $T, p$, representing the number of test cases and the modulus. For each test case:

• One line containing two integers $n, x$.

Output Format

For each test case:

• Output one positive integer per line, the number of essentially different failure states, taken modulo $p$.

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

8
0
12
34
20

Hint

[Sample Explanation #1]

For the first test case, $n = 3$, $x = 4$:

• Considering only the grid states, there are $6$ possible failures: $[8, 4, 2], [2, 4, 8], [2, 8, 4], [4, 8, 2], [2, 8, 2], [2, 4, 2]$.
  • But consider $[2, 8, 2]$. It can correspond to two essentially different failure states:
    • The middle $8$ is generated first, then the left $2$ is generated, then the right $2$ is generated.
    • The middle $8$ is generated first, then the right $2$ is generated, then the left $2$ is generated.
  • The same applies to $[2, 4, 2]$.
• For the other possibilities, it can be proven that each corresponds to only one essentially different failure state.
• Therefore, the answer is $1 + 1 + 1 + 1 + 2 + 2 = 8$, which is $8$ modulo $71$.

For the second test case, $n = 4$, $x = 3$:

• It can be proven that no matter what, the game will always be won, so there are no failure states and the answer is $0$.

For the third test case, $n = 4$, $x = 4$:

• Considering only the grid states, there are $4$ possible failures: $[2, 8, 4, 2], [2, 4, 8, 2], [4, 8, 4, 2], [2, 4, 8, 4]$.
• Among them, $[2, 8, 4, 2]$ and $[2, 4, 8, 2]$ each correspond to $4$ essentially different failures, while $[4, 8, 4, 2]$ and $[2, 4, 8, 4]$ each correspond to $2$ essentially different failures.
  • Take $[2, 8, 4, 2]$ as an example. The $4$ essentially different failures corresponding to this position are listed below (the operation sequence is not unique; the small numbers above the tiles denote appearance times):$$\begin{aligned} & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{R}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] & \stackrel{\text{R}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{\hspace{15.385mu}}{}, \overset{13}{2}] & \stackrel{\text{R}}\to& [\overset{13}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{11}{2}, \overset{13}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{11}{2}, \overset{13}{2}] \\ \stackrel{\text{R}}\to& [\overset{15}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{13}{2}] & \stackrel{\text{L}}\to& [\overset{13}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{15}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{14}{4}, \overset{15}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{14}{4}, \overset{15}{2}] \end{aligned}$$For these $4$ cases, the order relations of appearance times (after discretization) are $[4, 1, 2, 3]$, $[3, 1, 2, 4]$, $[2, 1, 3, 4]$, and $[1, 2, 3, 4]$, respectively.
• Therefore, the answer is $4 + 4 + 2 + 2 = 12$, which is $12$ modulo $71$.

For the fourth test case, $n = 4$, $x = 5$:

• It can be proven that the answer is $34$, which is $34$ modulo $71$.

For the fifth test case, $n = 5$, $x = 6$:

• It can be proven that the answer is $162$, which is $20$ modulo $71$.

[Sample #2]

See game/game2.in and game/game2.ans in the attachment.

This sample set satisfies the constraints of test points $3 \sim 5$.

[Sample #3]

See game/game3.in and game/game3.ans in the attachment.

This sample set satisfies the constraints of test points $6 \sim 10$.

[Sample #4]

See game/game4.in and game/game4.ans in the attachment.

This sample set satisfies the constraints of test points $14 \sim 17$.

[Sample #5]

See game/game5.in and game/game5.ans in the attachment.

This sample set satisfies the constraints of test points $22 \sim 25$.

[Constraints]

This problem has $25$ test points, $4$ points each.

For all data, it is guaranteed that $1 \le T \le 10^5$, $1 \le n, x \le 300$, and $2 \le p \le 10^9$.

Translated by ChatGPT 5