Into the woods

Not all who wander are lost.

Perhaps it's just taking a walk, or perhaps it's for escaping from something. Roundgod temporarily left the city he used to live in and headed to a boundless forest.

Roundgod then began to wander in the forest. If we consider the forest as a two-dimensional Cartesian plane, then Roundgod starts from $(0,0)$, and each time he chooses one of the four directions uniformly at random and moves one step forward(i.e.,the possible changes of Roundgod's coordinates are $(-1,0),(1,0),(0,-1),(0,1)$). After Roundgod took $n$ steps, he stopped, in a trance, realizing that he had been wandering for too long and that it was time to return to his casual life. Now there's only one remaining problem that he wonders: During the $n$ steps he moved, how far he was from the starting point? As Roundgod has forgotten the moves he has taken, he only wants to know the expected answer for all his possible routes.

Formally, Roundgod starts from $(0,0)$, each time chooses one of the four directions uniformly at random and moves one step forward. You should calculate, among all his $4^n$ possible routes, the expected maximum Manhattan distance between any position on his route and $(0,0)$.

Specifically, the Manhattan distance between two points $p_1=(x_1,y_1)$ and $p_2=(x_2,y_2)$ in the Cartesian plane is defined as $d(p_1,p_2)=\vert x_1-x_2\vert +\vert y_1-y_2\vert$. Also, for any prime modular $10^8\leq MOD\leq 10^9+7$, we can prove that the answer can be written as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers and $Q\not\equiv 0\pmod {MOD}$. You need to output $P\cdot Q^{-1}\pmod{MOD}$ as the answer, where $Q^{-1}\pmod{MOD}$ represents the modular inverse of $Q$ with respect to $MOD$.

The first line contains a number $T(1\leq T \leq 10)$, denoting the number of test cases.

The first line of each test case contains two numbers $n, MOD(1\leq n\leq 10^6, 10^8\leq MOD\leq 10^9+7)$, denoting the number of steps taken and the modular. It is guaranteed that $MOD$ is prime.

For each test case, output one integer in a line, denoting the answer.

3
1 1000000007
2 998244353
50 1000000007

1
249561090
603242629

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）