ACM-ICPC-OJ训练营

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.

1836: Rikka with Rock-paper-scissors

题目描述

输入描述

输出描述

样例输入

样例输出

来源