Factorial Again

4.7

7 votes
Mathematics, Medium, Open, Approved, Number Theory
Problem

Kate has finally calmed down and decides to forgive Little Deepu, but she won't forgive him just like that. She agrees to forgive him on the grounds that he can solve a mathematical question for her.
She gives Deepu a large number N and a prime number P and asks him to calculate ((3*N)! / (3!^N) )%P.
Your task is to help Little Deepu get back together with Kate.

Input
First line contains number of test cases T.
Next T lines contain two integers N and P, where P is a prime.

Output
For each test case output the result ( (3*N)! / (3!)N ) % P.

Constraints:
1 ≤ T ≤ 10000
1 ≤ N ≤ 333333333
1 ≤ P ≤ 1000000000
1 ≤ abs(3*N-P) ≤ 1000

Sample Input
2
3 11
2 11
Sample Output
8
9
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?