Read problems statements in Mandarin Chinese and Russian as well. 
You are given a function f which is defined as :
 
Your task is to find the value of 
 
where M is given in input.

------ Input Format ------ 

First line contains T, the number of test cases.

First line of each test case contain 3 space separated integers N, M and Q.

Next Q line follows, each line contain r.

------ Output Format ------ 

For each test case, output Q lines, each line containing the required answer.

------ Constraints ------ 

2 ≤ N ≤ 10^{6}

1 ≤ M ≤ 10^{9}

2 ≤ Sum of N over all test cases ≤ 10^{6}

1 ≤ Sum of Q over all test cases ≤ 2*10^{5}

1 ≤ T ≤ 10^{5}

1 < r < N

Sample Input
2
5 114 1
2
50 3874 3
31
17
21

Sample Output
72
3718
624
1144

Explanation for first test case 
f[1] = 1

f[2] = 2

f[3] = 1*2^{2} * 3 = 12

f[4] =1*2^{3}*3^{2}*4 = 8*9*4 = 288

f[5] = 1*2^{4}*3^{3}*4^{2}*5 =34560

value of f[5] / (f[2]*f[3]) = 1440 and 1440 %114 is 72

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Mathematics


Solutions:
for _ in range(int(input())):
	(n, mod, q) = map(int, input().split())
	ls = [0] * n
	ls[1] = n
	for i in range(2, n):
		ls[1] = ls[1] * i % mod
	n += 1
	if n % 2:
		(num, den, cur) = (n // 2 + 1, n // 2, n // 2 + 1)
	else:
		(num, den, cur) = (n // 2, n // 2, 1)
	n -= 1
	ls[den] = cur
	num += 1
	den -= 1
	while den > 1:
		cur = cur * (den + 1) % mod
		cur = cur * num % mod
		ls[den] = cur
		num += 1
		den -= 1
	for i in range(2, n // 2 + 1):
		ls[i] = ls[i] * ls[i - 1] % mod
	for __ in range(q):
		x = int(input())
		if x > n / 2:
			x = n - x
		print(ls[x])


t = int(input())
for each_t in range(t):
	(n, m, q) = input().split()
	(n, m, q) = (int(n), int(m), int(q))
	a = [0] * (n + 1)
	if n % 2 == 0:
		mid = n // 2
		a[mid] = mid + 1
		b = mid
		c = mid + 2
	else:
		mid = n // 2 + 1
		a[mid] = 1
		b = mid
		c = mid + 1
	x = mid - 1
	while x >= 1:
		a[x] = a[x + 1] % m * b % m * c % m % m
		b -= 1
		c += 1
		x -= 1
	a[0] = 1
	for i in range(1, mid + 1):
		a[i] = a[i - 1] * a[i] % m
	for each_q in range(q):
		r = int(input())
		r = min(r, n - r)
		print(a[r] % m)