You are currently studying the language $A j o b$ ( which means strange in English ) from a renowned professor. The language has infinite number of letters in its alphabet ( now you know, why it is called ajob ).  

The professor taught you $N$ words, one by one. The number of letters in a word is equal to it's place in the teaching order. Thus, the $1^{st}$ word taught by the professor has $\mbox{1}$ letter, $2^{nd}$ word has $2$ letters, $3^{rd}$ word has $3$ letters, $\ldots$, the $N^{th}$ word has $N$ letters.  

All the letters within a word are distinct to each other.

Now, you are handed an assignment. You have to choose any one of the $N$ words and form a subsequence from it. The length of the subsequence should be exactly $\mbox{K}$ less than the length of original word. For example, if the length of the chosen word is $\mbox{L}$, then the length of the subsequence should be $L-K$. If for any word, $\mbox{L}$ is smaller than $\mbox{K}$ $\left(L<K\right)$, then you must not choose that word. Two subsequences are different to each other if, the lengths of them are different or they contain different characters in the same position.

Find the number of ways you can complete the assignment ${modulo}\:p$ ( ${p}$ will always be a $\textit{prime}$ ).  

1. 

The first line contains ${T}$, the number of testcases. The next ${T}$ lines contain three space separated integers $N$, ${K}$ and ${p}$.  

Output Format 

For each testcase, print one integer in a single line, the number possible ways you can complete the assignment, ${modulo}\:p$.

Constraints 

$1\leq T\leq100$ 

$2\leq N\leq10^{18}$ 

$0<K<N$ 

$2\leq p\leq10^5$ 

$p\:\text{is a Prime}$  

Sample Input #00  

3
2 1 2
2 1 5
5 3 13

Sample Output #00  

1
3
2

Sample Input #01  

5
5 2 3
6 5 11
7 6 3
6 5 7
6 5 5

Sample Output #01  

2
7
2
0
2

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


import math

def ext_gcd(aneek, sayantan):
	ash = aneek // sayantan
	champa = aneek - sayantan * ash
	shreejit = [1, 0]
	while champa != 0:
		aneek = sayantan
		sayantan = champa
		shreejit.append(shreejit[0] - ash * shreejit[1])
		shreejit = shreejit[1:]
		ash = aneek // sayantan
		champa = aneek - sayantan * ash
	return shreejit[1]

def inv_mod(xavi, prime):
	barca = ext_gcd(xavi, prime)
	if barca < 0:
		barca += prime
	return barca

def C1(n, m, p):
	if m == 0 or n == m:
		return 1
	elif m == 1 or n - m == 1:
		return n % p
	else:
		ans = 1
		ind = 1
		q1 = m
		q2 = n
		while ind != 0:
			m_i = q1 % p
			n_i = q2 % p
			q1 = q1 // p
			q2 = q2 // p
			ind = q1
			if m_i > n_i:
				return 0
			elif m_i == 0 or n_i == m_i:
				continue
			elif m_i == 1 or n_i == m_i + 1:
				ans = ans * n_i % p
			else:
				m_i = min(m_i, n_i - m_i)
				tmp = 1
				for j in range(m_i):
					tmp = tmp * (n_i - j) % p
					tmp = tmp * inv_mod(j + 1, p) % p
				ans = ans * tmp % p
		return ans
t = int(input())
for i in range(t):
	s = input().strip().split()
	n = int(s[0])
	k = int(s[1])
	p = int(s[2])
	print(C1(n + 1, k + 1, p))


T = int(input())
for t in range(T):
	(N, K, p) = map(int, input().split())
	N += 1
	K += 1
	C = 1
	while K:
		(N, n) = divmod(N, p)
		(K, k) = divmod(K, p)
		if n < k:
			C = 0
			break
		if n < 2 * k:
			k = n - k
		a = 1
		b = 1
		for i in range(k):
			a = a * (n - i) % p
			b = b * (i + 1) % p
		C = C * a * pow(b, p - 2, p) % p
	print(C)


def moduloArr(p):
	ret = [1]
	for i in range(1, p):
		ret.append(ret[-1] * i % p)
	return ret

def counter(mArr, n, p):
	c = 0
	r = 1
	while n > 0:
		r *= mArr[n % p]
		n //= p
		c += n
	return (c, r)

def solve(n, k, p):
	l = n - k
	mArr = moduloArr(p)
	(c1, r1) = counter(mArr, n + 1, p)
	(c2, r2) = counter(mArr, k + 1, p)
	(c3, r3) = counter(mArr, l, p)
	if c1 - c2 - c3 > 0:
		return 0
	r2 = pow(r2, p - 2, p)
	r3 = pow(r3, p - 2, p)
	return r1 * r2 * r3 % p
t = int(input())
while t > 0:
	(n, k, p) = map(int, input().rstrip().split())
	print(solve(n, k, p))
	t -= 1


(F, p) = ([1] * 100000, 0)

def powM(b, e):
	return 1 if e == 0 else b if e == 1 else powM(b, e >> 1) ** 2 * b % p if e & 1 else powM(b, e >> 1) ** 2 % p

def C(n, m):
	return C(n % p, m % p) * C(n // p, m // p) % p if n >= p or m >= p else 0 if n < m else F[n] * powM(F[n - m], p - 2) % p * powM(F[m], p - 2) % p
for _ in range(int(input())):
	(N, K, p) = map(int, input().split(' '))
	for i in range(2, p):
		F[i] = F[i - 1] * i % p
	print(C(N + 1, K + 1))


def inv(n):
	return pow(n, P - 2, P)

def fact_val(n):
	q = P
	v = 0
	while q <= n:
		v += n // q
		q *= P
	return v

def fact(n):
	if n < P:
		return Fact[n]
	(q, r) = divmod(n, P)
	return pow(Fact[P - 1], q, P) * fact(q) * Fact[r] % P

def binom(n, p):
	assert 0 <= p <= n
	A = fact(n) * inv(fact(p) * fact(n - p) % P) % P
	v = fact_val(n) - fact_val(p) - fact_val(n - p)
	return 0 if v > 0 else A
T = int(input())
for _ in range(T):
	(N, K, P) = map(int, input().split())
	Fact = [1] * P
	for i in range(2, P):
		Fact[i] = Fact[i - 1] * i % P
	print(binom(N + 1, K + 1))


import os, sys, math

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def base_p(n, p):
	a = []
	while n != 0:
		(q, r) = divmod(n, p)
		a.append(r)
		n = q
	return a

def binomial_is_div_by_prime(n, r, p):
	(q1, q2) = (n, r)
	while q2 != 0:
		(q1, r1) = divmod(q1, p)
		(q2, r2) = divmod(q2, p)
		if r2 > r1:
			return True
	return False

def mod_binomial_small(n, k, p):
	if n - k < k:
		k = n - k
	r = 1
	for i in range(k):
		r = r * (n - i) % p
		r = r * modular_inverse(1 + i, p) % p
	return r

def mod_binomial(n, r, p):
	if r < 0 or r > n:
		return 0
	an = base_p(n, p)
	ar = base_p(r, p)
	for i in range(len(ar)):
		if ar[i] > an[i]:
			return 0
	if len(an) < len(ar):
		an += [0] * (len(ar) - len(an))
	elif len(ar) < len(an):
		ar += [0] * (len(an) - len(ar))
	luc = 1
	bin_cache = {}
	for (nd, rd) in zip(an, ar):
		y = bin_cache.get((nd, rd))
		if y is None:
			y = bin_cache[nd, rd] = mod_binomial_small(nd, rd, p)
		luc = luc * y % p
	return luc

def solve(N, m, p):
	return mod_binomial(N + 1, m + 1, p)

def main():
	t = int(sys.stdin.readline())
	for t_itr in range(t):
		nrm = sys.stdin.readline().split()
		(N, k, p) = (int(nrm[0]), int(nrm[1]), int(nrm[2]))
		result = solve(N, k, p)
		print(result)
main()


def inv(n):
	return pow(n, P - 2, P)

def fact_val(n):
	q = P
	v = 0
	while q <= n:
		v += n // q
		q *= P
	return v

def fact(n):
	if n < P:
		return Fact[n]
	(q, r) = divmod(n, P)
	return pow(Fact[P - 1], q, P) * fact(q) * Fact[r] % P

def binom(n, p):
	assert 0 <= p <= n
	A = fact(n) * inv(fact(p) * fact(n - p) % P) % P
	v = fact_val(n) - fact_val(p) - fact_val(n - p)
	return 0 if v > 0 else A
T = int(input())
for _ in range(T):
	(N, K, P) = map(int, input().split())
	Fact = [1] * P
	for i in range(2, P):
		Fact[i] = Fact[i - 1] * i % P
	print(binom(N + 1, K + 1))


def invmod(a, n):
	(b, c) = (1, 0)
	while n:
		(q, r) = divmod(a, n)
		(a, b, c, n) = (n, c, b - q * c, r)
	return b

def mega_fact(n, p, facts):
	if n < p:
		return facts[n]
	ans = mega_fact(n // p, p, facts) * facts[n % p] % p
	if n // p % 2 != 0:
		ans = p - ans
	return ans
for _ in range(int(input())):
	(N, K, p) = list(map(int, input().split()))
	num = N + 1
	denom = K + 1
	zero = False
	while num > 0:
		if num % p < denom % p:
			zero = True
			break
		num = num // p
		denom = denom // p
	if zero:
		print(0)
		continue
	facts = [1]
	for i in range(1, p):
		while i % p == 0:
			i = i // p
		facts.append(facts[-1] * i % p)
	ans = mega_fact(N + 1, p, facts)
	denom = mega_fact(K + 1, p, facts)
	denom = denom * mega_fact(N - K, p, facts) % p
	denom = invmod(denom, p)
	ans = ans * denom % p
	print(ans)


maxprime = 100000
isprime = [True] * maxprime
primelist = []
for i in range(2, maxprime):
	if isprime[i]:
		primelist.append(i)
		for j in range(i * i, maxprime, i):
			isprime[j] = False
t = int(input())
for _ in range(t):
	[n, k, p] = list(map(int, input().split(' ')))
	factlist = [1]
	factinv = [1] * p
	for i in range(1, p):
		factlist.append(factlist[-1] * i % p)
	factinv = [1] * p
	for i in range(p):
		if i % 2 == 0:
			factinv[i] = factlist[p - i - 1]
		else:
			factinv[i] = p - factlist[p - i - 1]
	currn = n + 1
	currk = k + 1
	toprint = 1
	while currn > 0:
		ndig = currn % p
		kdig = currk % p
		if kdig > ndig:
			toprint = 0
			break
		else:
			toprint = toprint * factlist[ndig] % p * (factinv[kdig] * factinv[ndig - kdig]) % p % p
		currn //= p
		currk //= p
	print(toprint)


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		a = A % p
		b = B % p
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


def modp_iter(n, p):
	value = 1
	for i in range(1, n + 1):
		yield value
		value = value * i % p
	yield value

class ModpFac:

	def __init__(self, p):
		self.fac = list(modp_iter(p - 1, p))
		self.p = p

	def get(self, i, pm):
		result = self.fac[i]
		if pm == 1:
			result = self.p - result
		return result

	def inv(self, i, pm):
		j = self.p - 1 - i
		pm = (pm + j + 1) % 2
		return self.get(j, pm)

def prod_mod_p(it, f, p):
	result = 1
	for (i, pm) in it:
		result = result * f(i, pm) % p
	return result

def decomposition2(x, p):
	a = x % p
	b = x // p
	if b == 0:
		return (0, [(a, b % 2)])
	else:
		(m0, a0) = decomposition2(b, p)
		a0.append((a, b % 2))
		return (m0 + b, a0)

def choose_mod_p(n, k, p):
	fac = ModpFac(p)
	(nm, na) = decomposition2(n, p)
	(km, ka) = decomposition2(k, p)
	(lm, la) = decomposition2(n - k, p)
	if nm > km + lm:
		return 0
	return prod_mod_p(na, fac.get, p) * prod_mod_p(ka, fac.inv, p) * prod_mod_p(la, fac.inv, p) % p

def count_cases(data):
	(n, k, p) = data
	return choose_mod_p(n + 1, k + 1, p)
t = int(input())
result = [count_cases(map(int, input().split())) for _ in range(t)]
print(*result, sep='\n')


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


def solve(N, K, p):
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)

	def calc(n, k):
		n %= p
		k %= p
		return 0 if n < k else f[n] * pow(f[n - k] * f[k], p - 2, p)
	N += 1
	K += 1
	r = 1
	while N and K and r:
		r *= calc(N, K)
		N //= p
		K //= p
	return r % p
for _ in range(int(input().strip())):
	(N, K, p) = map(int, input().rstrip().split())
	print(solve(N, K, p))


memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


memo = {}

def C(n, k, p):
	fact = [1]
	for i in range(1, p):
		fact.append(fact[-1] * i % p)
	if p in memo:
		inv_fact = memo[p]
	else:
		inv = [0, 1]
		for i in range(2, p):
			inv.append(p - p // i * inv[p % i] % p)
		inv_fact = [1]
		for i in range(1, p):
			inv_fact.append(inv_fact[-1] * inv[i] % p)
		memo[p] = inv_fact
	ret = 1
	while n > 0:
		n1 = n % p
		k1 = k % p
		if k1 > n1:
			return 0
		ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
		n //= p
		k //= p
	return ret
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	print(C(n + 1, k + 1, p))


import os
import sys
import math

def C(n, r, p):
	if r < 0 or r > n:
		return 0
	if r == 0 or r == n:
		return 1
	if n >= p:
		return C(n // p, r // p, p) * C(n % p, r % p, p) % p
	r = min(r, n - r)
	product = 1
	product = fact[n] * pow(fact[n - r], p - 2, p) % p * pow(fact[r], p - 2, p) % p
	return product
t = int(input())
for i in range(t):
	a = list(map(int, input().rstrip().split()))
	fact = [1] * (a[2] + 1)
	for i in range(2, a[2] + 1):
		fact[i] = fact[i - 1] * i % a[2]
	print(C(a[0] + 1, a[0] - a[1], a[2]))


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			print(0)
			break
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	else:
		print(res)


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def solve(n, r, p):
	dp = [1]
	for i in range(1, p):
		dp.append(dp[-1] * i % p)
	res = 1
	while n or r:
		a = n % p
		b = r % p
		n //= p
		r //= p
		if a < b:
			return 0
		res *= dp[a] * pow(dp[b] * dp[a - b] % p, p - 2, p) % p
		res %= p
	return res
t = int(input())
while t > 0:
	(n, k, p) = map(int, input().split())
	ans = solve(n + 1, k + 1, p)
	print(ans)
	t = t - 1


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())


t = int(input())

def sol():
	(n, k, p) = map(int, input().strip().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for i in range(t):
	print(sol())


import sys

def go():
	(n, k, p) = map(int, sys.stdin.readline().split())
	A = n + 1
	B = k + 1
	res = 1
	f = [1]
	for i in range(1, p):
		f.append(f[-1] * i % p)
	while A or B:
		(a, b) = (A % p, B % p)
		A //= p
		B //= p
		if a < b:
			return 0
		res *= f[a] * pow(f[b] * f[a - b] % p, p - 2, p)
		res %= p
	return res
for _ in range(int(sys.stdin.readline())):
	print(go())