P8991 - Auspiciousness

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：8 通过：0

Dog Card is a card game. In the game, there are a total of

2 n

cards in the deck, each card has a value, and the values of these

2 n

cards form a permutation of

1∼2n1\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

(2 n)!

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≤t≤3001\le t\le 300$ ) — the number of test cases.
	


	
		Each test case consists of one line containing two integers  $n$  ( $1≤n≤3001\le n\le 300$ ) and  $m$  ( $2≤m≤1092\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

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≤n1\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≤n2\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.

2023牛客暑期多校训练营3

8991: Auspiciousness

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签