Cuber QQ has encountered a math problem during his research of "nothing related to math", he thought the problem too boring for him, and decided to leave it to you. You might be curious about more background about why this problem appeared in his research, but to save your time, let's say "the background isn't helpful for you to solve this problem".
Given nn, mm, count the number of sequence x1,x2,…,xnx1,x2,…,xn such that x21+x22+⋯+x2n−1≡x2n(modm)x12+x22+⋯+xn−12≡xn2(modm) and 0≤xi<m0≤xi<m for 1≤i≤n1≤i≤n. mm is odd in this problem.
Input
The first line of the input is an integer tt (1≤t≤25001≤t≤2500), where tt is the number of test cases.
Then follows tt test cases, each of which is a line with two space-separated integers nn and mm (3≤n≤100,3≤m≤999 999 9993≤n≤100,3≤m≤999 999 999 and mm is odd).
Output
For each test case, output the answer modulo 109+7109+7.