Fombinatorial

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a function f which is defined as :
Your task is to find the value of f(N) / ( f(r)*f(Nr) )
. As it will be a large number output it modulo M.
Input
First line contains T , number of test cases to follow.
Next follows T test case.
First line of ever test case contain 3 space separated integers N , M and Q.
Next Q line follows , each line contain r.
Output
For every test case , output Q lines , each line containing the answer.
Constraints
 2 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{9}
 2 ≤ Sum of N over all test cases ≤ 5*10^{5}
 2 ≤ Sum of Q over all test cases ≤ 10^{5}
 1 < r < N
Subtasks
 Subtask 1: N ≤ 5 , rest of the constraints are same. Points  9
 Subtask 2: N ≤ 500 , M is a prime number , rest of the constraints are same. Points  31
 Subtask 3: Refer to constraints above : Points60
Sample Input
1 5 24 2 2 3Sample Output
8 8
Explanation
f[1] = 1
f[2] = 4
f[3] = 1*2^{2}*3^{3} = 108
f[4] =1*2^{2}*3^{3}*4^{4} = 27648
f[5] = 1*2^{2}*3^{3}*4^{4}*5^{5} =86400000
value of f[5] / (f[2]*f[3]) = 200000 and 200000%24 is 8
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/POWERMUL 
Tags  devuy11, easymedium, nov14, numbertheory 
Date Added:  21072014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 