B-Auspiciousness_2026牛客五一集训派对day1

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Dog Card is a card game. In the game, there are a total of $2n$ cards in the deck, each card has a value, and the values of these $2n$ cards form a permutation of $1\sim 2n$ . There is a skill that works as follows:

Draw a card from the top of the deck.
If the deck is empty, then skip to step $3$ , otherwise you guess whether the card on the top of the deck has a higher value than your last drawn card and draw a card from the top of the deck. If your guess is correct, then repeat this step, otherwise skip to step 3.
End this process.

Nana enjoys playing this game, although she may not be skilled at it. Therefore, her guessing strategy when using this skill is simple: if the value of the last drawn card is less than or equal to $n$ , then she guesses that the next card's value is higher; otherwise, she guesses that the next card's value is lower. She wants to know, for all different decks of cards (Obviously, there are $(2n)!$ cases), how many cards she can draw in total if she uses the skill only once in each case. Since this number can be very large, please provide the answer modulo a given value.

输入描述:

The first line contains a single integer $t$ ( $1\le t\le 300$ ) — the number of test cases.

Each test case consists of one line containing two integers $n$ ( $1\le n\le 300$ ) and $m$ ( $2\le m\le 10^9$ ), denoting half the total number of cards in the deck and the modulus respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300$ .

输出描述:

For each test case, print one integer — the total number of cards Nana can draw modulo $m$ .

示例1

输入

复制

输出

复制

4
84
3084

备注:

For example, if $n=2$ and the values of cards from the top to the bottom are $1,2,4,3$ , Nana can draw all cards by using the skill only once. The process is as follows:

Draw the card of value $1$ .
For $1\le n$ , she guesses that the next card has a higher value and draws the card of value $2$ .
Her guess is correct. For $2\le n$ , she guesses that the next card has a higher value and draws the card of value $4$ .
Her guess is correct. For $4>n$ , she guesses that the next card has a lower value and draws the card of value $3$ .

Note that if the values of cards from the top to the bottom are $1,2,3,4$ , although her last guess is wrong, she can draw all cards too according to the skill.