ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 A: Auspiciousness

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：8 通过：0
返回比赛提交提交记录

题目描述

Dog Card is a card game. In the game, there are a total of 2n2n2n cards in the deck, each card has a value, and the values of these 2n2n2n cards form a permutation of 1∼2n1\sim 2n1∼2n. There is a skill that works as follows:
  1. Draw a card from the top of the deck.
  2. If the deck is empty, then skip to step 333, 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.
  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 nnn, 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)!(2n)!(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 ttt (1≤t≤3001\le t\le 3001≤t≤300) — the number of test cases.
	


	
		Each test case consists of one line containing two integers nnn (1≤n≤3001\le n\le 3001≤n≤300) and mmm (2≤m≤1092\le m\le 10^92≤m≤109), denoting half the total number of cards in the deck and the modulus respectively.
	


	
		It is guaranteed that the sum of nnn over all test cases does not exceed 300300300.

输出格式

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

输入样例 复制 

3
1 1000000
2 1000000
3 1000000

输出样例 复制 

4
84
3084

数据范围与提示


For example, if n=2n=2n=2 and the values of cards from the top to the bottom are 1,2,4,31,2,4,31,2,4,3, Nana can draw all cards by using the skill only once. The process is as follows:
  • Draw the card of value 111.
  • For 1≤n1\le n1≤n, she guesses that the next card has a higher value and draws the card of value 222.
  • Her guess is correct. For 2≤n2\le n2≤n, she guesses that the next card has a higher value and draws the card of value 444.
  • Her guess is correct. For 4>n4>n4>n, she guesses that the next card has a lower value and draws the card of value 333.
Note that if the values of cards from the top to the bottom are 1,2,3,41,2,3,41,2,3,4, although her last guess is wrong, she can draw all cards too according to the skill.

分类标签