Responsive image

问题 D: Rikka with Rock-paper-scissors

问题 D: Rikka with Rock-paper-scissors

时间限制: 20 Sec  内存限制: 128 MB
提交: 3  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Alice and Bob are going to play a famous game: Rock-paper-scissors. Both of them don’t like to think a lot, so both of them will use the random strategy: choose rock/paper/scissors in equal probability. 

They want to play this game n times, then they will calculate the score s in the following way: if Alice wins a times, Bob wins b times, and in the remaining n−a−bgames they make a tie, the score will be the greatest common divisor of a and b.

Know Yuta wants to know the expected value of s×32n. It is easy to find that the answer must be an integer.

It is too difficult for Rikka. Can you help her?

Note: If one of a,b is 0, we define the greatest common divisor of a and b as a+b.

输入描述

The first line contains a number t(1≤t≤20), the number of the testcases. There are no more than 2 testcases with n≥104.
For each testcase, the first line contains two numbers n,mo(1≤n≤105,108≤mo≤109)
It is guaranteed that mo is a prime number.

输出描述

For each testcase, print a single line with a single number -- the answer modulo mo.

样例输入

5
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353

样例输出

6
90
972
9720
89910
[提交][状态]
ACM算法攻关部