Waiter: Good day, sir! What would you like to order? 

Lucas: One Cheese & Random Toppings (CRT) pizza for me, please. 

Waiter: Very good, sir. There are $N$ toppings to choose from, but you can choose only ${R}$ toppings. 

Lucas: Hmm, let's see...  

...Then Lucas started writing down all the ways to choose R toppings from N toppings in a piece of napkin. Soon he realized that it's impossible to write them all, because there are a lot. So he asked himself: How many ways are there to choose exactly ${R}$ toppings from $N$ toppings?

Since Lucas doesn't have all the time in the world, he only wished to calculate the answer modulo ${M}$, where M is a squarefree number whose prime factors are each less than 50.

Fortunately, Lucas has a Wi-Fi-enabled laptop with him, so he checked the internet and discovered the following useful links: 

Lucas' theorem 

Chinese remainder theorem (CRT)  

Input Format 

The first line of input contains ${T}$, the number of test cases. The following lines describe the test cases.

Each test case consists of one line containing three space-separated integers: $N$, ${R}$ and ${M}$.  

Constraints 

$1\leq T\leq200$ 

$1\leq M\leq10^9$ 

$1\leq R\leq N\leq10^9$ 

${M}$ is squarefree and its prime factors are less than $50$

Output Format 

For each test case, output one line containing a single integer: the number of ways to choose ${R}$ toppings from $N$ toppings, modulo ${M}$.  

Sample Input  

6
5 2 1001
5 2 6
10 5 15
20 6 210
13 11 21
10 9 5    

Sample Output  

10
4
12
120
15
0

Explanation  

Case 1 and 2: Lucas wants to choose 2 toppings from 5 toppings. There are ten ways, namely (assuming the toppings are A, B, C, D and E):  

AB, AC, AD, AE, BC, BD, BE, CD, CE, DE  

Thus, 

Case 1: $10\:{mod}\:1001=10$ 

Case 2: $10\:{mod}\:6=4$  

Case 6: We can choose 9 toppings from 10 by removing only one from our choice. Thus, we have ten ways and $10\:{mod}\:5=0$

Source: hackerrank | Difficulty: EASY
Tags: Number theory


Solutions:
import sys, random
from math import sqrt

def fact_p_count(n, p):
	n //= p
	m = n
	while n >= p:
		n //= p
		m += n
	return m

def mod_inverse(n, s=0):
	if s == 0:
		s = n - 1
	inv = [0] * (s + 1)
	inv[1] = 1
	for i in range(2, s + 1):
		inv[i] = inv[n % i] * (n - n // i) % n
	return inv

def pollard_rho(N, rand=random.randint):
	if N & 1 == 0:
		return 2
	(y, c, m) = (rand(1, N - 1), rand(1, N - 1), 250)
	while c == N - 2:
		c = rand(1, N - 1)
	(g, r, q) = (1, 1, 1)
	while g == 1:
		x = y
		for i in range(r):
			y = (y * y + c) % N
		for k in range(0, r, m):
			ys = y
			for _ in range(min(m, r - k)):
				y = (y * y + c) % N
				q = q * (y - x) % N
			g = gcd(q, N)
			if g != 1:
				break
		r <<= 1
	if g == N:
		g = 1
		while g == 1:
			ys = (ys * ys + c) % N
			g = gcd(x - ys, N)
	return g

def factors(n):
	if n <= 1:
		return []
	PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031]
	ret = []
	two = n & -n
	e = two.bit_length() - 1
	if e > 0:
		ret.append((2, e))
		n >>= e
	p_max = int(n ** 0.5)
	for p in PRIMES[1:]:
		if p > p_max:
			break
		(q, r) = divmod(n, p)
		if r:
			continue
		e = 1
		n = q
		while 1:
			(q, r) = divmod(n, p)
			if r:
				break
			e += 1
			n = q
		ret.append((p, e))
		p_max = int(n ** 0.5)
	if n > 1:
		if p_max <= PRIMES[-1] or miller_rabin(n):
			ret.append((int(n), 1))
		else:
			large_primes = []
			threshold = PRIMES[-1] ** 2
			while 1:
				p = pollard_rho(n)
				if not miller_rabin(p):
					continue
				n //= p
				e = 1
				while 1:
					(q, r) = divmod(n, p)
					if r:
						break
					n = q
					e += 1
				large_primes.append((int(p), e))
				if n <= threshold or miller_rabin(n):
					if n > 1:
						large_primes.append((int(n), 1))
					break
			ret += sorted(large_primes)
	return ret

def extgcd(x, y, z=1):
	(q, r) = divmod(x, y)
	if r != 0:
		(x, y) = extgcd(y, r, z)
		return (y, x - y * q)
	else:
		return (0, z)

def binomial_p(n, m, p, facts=[], inv_facts=[]):
	if n < 0 or m < 0 or m > n or (p == 1):
		return 0
	rems_n = []
	rems_m = []
	while n > 0:
		rems_n.append(n % p)
		rems_m.append(m % p)
		n //= p
		m //= p
	if len(facts) == 0:
		size = max(max(rems_n), max(rems_m))
		invs = mod_inverse(p, size)
		facts = [1] * (size + 1)
		inv_facts = [1] * (size + 1)
		for i in range(1, size + 1):
			facts[i] = facts[i - 1] * i % p
			inv_facts[i] = inv_facts[i - 1] * invs[i] % p
	ret = 1
	for (n1, d1) in zip(rems_n, rems_m):
		if n1 < d1:
			ret = 0
			break
		ret = ret * facts[n1] * inv_facts[d1] * inv_facts[n1 - d1] % p
	return ret

def calc_fact_p(n, p, q, facts, fact_p, inv_fact_p):
	if n < p * q:
		return fact_p[n]
	u = n // p
	v = n - u * p
	r = (q + 1) // 2
	mod = p ** q
	phi = (p - 1) * p ** (q - 1)
	ret = fact_p[v]
	beta_numer = u
	for j in range(1, r + 1):
		beta_numer *= (u - j) * (u + j)
	for j in range(1, r + 1):
		beta_denom = (u - j) * (u + j)
		beta_denom *= facts[j + r] * facts[r - j]
		if r - j & 1:
			beta_denom = -beta_denom
		beta = beta_numer * (2 * j) // beta_denom % phi
		ret = ret * pow(fact_p[j * p], beta, mod) % mod
	if p == 2:
		left_mod4 = ((u * p + 1 & 4) >> 1) + 1
		right_mod4 = ret & 3
		if left_mod4 != right_mod4:
			ret = (mod - ret) % mod
	alpha_numer = u
	for j in range(1, q):
		alpha_numer *= u - j
	for j in range(1, q):
		alpha_denom = (u - j) * facts[j] * facts[q - 1 - j]
		if q - 1 - j & 1:
			alpha_denom = -alpha_denom
		alpha = alpha_numer // alpha_denom % phi
		base = fact_p[j * p + v] * inv_fact_p[j * p] * inv_fact_p[v] % mod
		ret = ret * pow(base, alpha, mod) % mod
	return ret

def _binomial_pq_small(n, m, p, q, fact_p, inv_fact_p):
	mod = p ** q
	r = n - m
	ret = 1
	if len(fact_p) == 0:
		required_size = 0
		(n_, m_, r_) = (n, m, r)
		while n_ > 0:
			required_size = max(required_size, n_ % mod)
			required_size = max(required_size, m_ % mod)
			required_size = max(required_size, r_ % mod)
			n_ //= p
			m_ //= p
			r_ //= p
		(fact_p, inv_fact_p) = make_fact_p(p, q, required_size + 1)
	ret = 1
	while n > 0:
		ret = ret * fact_p[n % mod] * inv_fact_p[m % mod] * inv_fact_p[r % mod] % mod
		n //= p
		m //= p
		r //= p
	return ret

def _binomial_pq_large(n, m, p, q, fact_p, inv_fact_p):
	mod = p ** q
	phi = (p - 1) * p ** (q - 1)
	r = n - m
	facts_size = (q + 1 & ~1) + 1
	facts = [1] * facts_size
	for i in range(1, facts_size):
		facts[i] = facts[i - 1] * i
	if len(fact_p) == 0:
		(fact_p, inv_fact_p) = make_fact_p(p, q, p * q)
	ret = 1
	while n > 0:
		n1 = calc_fact_p(n % mod, p, q, facts, fact_p, inv_fact_p) % mod
		d1 = calc_fact_p(m % mod, p, q, facts, fact_p, inv_fact_p) % mod
		d2 = calc_fact_p(r % mod, p, q, facts, fact_p, inv_fact_p) % mod
		ret = ret * n1 * pow(d1 * d2, phi - 1, mod) % mod
		n //= p
		m //= p
		r //= p
	return ret

def binomial_pq(n, m, p, q, fact_p=[], inv_fact_p=[]):
	if n < 0 or m < 0 or m > n or (p == 1):
		return 0
	r = n - m
	e0 = fact_p_count(n, p) - fact_p_count(m, p) - fact_p_count(r, p)
	if e0 >= q:
		return 0
	if q == 1:
		return binomial_p(n, m, p)
	mod = p ** q
	if mod <= 10 ** 4:
		ret = _binomial_pq_small(n, m, p, q, fact_p, inv_fact_p)
	else:
		ret = _binomial_pq_large(n, m, p, q, fact_p, inv_fact_p)
	eq1 = fact_p_count(n // (mod // p), p)
	eq1 -= fact_p_count(m // (mod // p), p)
	eq1 -= fact_p_count(r // (mod // p), p)
	if not (p == 2 and q >= 3) and eq1 & 1 == 1:
		ret = (mod - ret) % mod
	ret = ret * p ** e0 % mod
	return ret

def crt(ps, rems):
	rem = rems[0]
	pro = ps[0]
	for i in range(1, len(rems)):
		(a, b) = extgcd(pro, ps[i])
		rem = (ps[i] * b * rem + pro * a * rems[i]) % (pro * ps[i])
		pro *= ps[i]
	return rem

def binomial_mod(n, m, mod):
	if n < 0 or m < 0 or m > n or (mod == 1):
		return 0
	f = factors(mod)
	rems = []
	ps = []
	for (p, e) in f:
		rems.append(binomial_pq(n, m, p, e))
		ps.append(p ** e)
	return crt(ps, rems)

def solve():
	stdin = sys.stdin
	T = int(stdin.readline())
	mat = [[0, 1], [1, 1]]
	MOD = 10 ** 9 + 7
	for _ in range(T):
		(N, R, M) = map(int, stdin.readline().split())
		print(binomial_mod(N, R, M))
solve()


def C(n, k, mod, inv):
	if k > n:
		return 0
	res = 1
	for i in range(n, n - k, -1):
		res *= i
		res %= mod
	for i in range(1, k + 1):
		res *= inv[i]
		res %= mod
	return res

def powmod(x, n, mod):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * x % mod
		x = x * x % mod
		n //= 2
	return res

def CL(n, k, mod):
	inv = [0, 1]
	for i in range(2, mod):
		inv.append((mod - mod // i) * inv[mod % i] % mod)
	res = 1
	while n or k:
		res = res * C(n % mod, k % mod, mod, inv) % mod
		n //= mod
		k //= mod
	return res

def factorize(x):
	res = []
	i = 2
	while x > 1:
		if x % i == 0:
			res.append(i)
			x //= i
		i += 1
	return res

def solve(n, k, mod):
	fa = factorize(mod)
	fa.sort()
	x = []
	for f in fa:
		res = CL(n, k, f)
		for (i, y) in enumerate(fa):
			if y >= f:
				break
			res = (res + f - x[i]) % f
			res = res * powmod(y, f - 2, f) % f
		x.append(res)
	res = 0
	for i in range(len(x)):
		curr = 1
		for j in range(i):
			curr *= fa[j]
		res += curr * x[i]
		res %= mod
	return res
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split())
	print(solve(n, k, m))


from sys import stderr
primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)

def main():
	(ncases,) = readints()
	for _ in range(ncases):
		(n, r, m) = readints()
		print(solve(n, r, m))

def solve(n, r, m):
	ans = 0
	for p in primes:
		if m % p:
			continue
		rem = combmodp(n, r, p)
		(s, t) = extgcd(p, m // p)
		ans = (ans + rem * t * m // p) % m
	return ans

def extgcd(a, b):
	(s, t, s0, t0) = (0, 1, 1, 0)
	while b > 0:
		q = a // b
		(b, a) = (a % b, b)
		(s, s0) = (s0 - q * s, s)
		(t, t0) = (t0 - q * t, t)
	return (s0, t0)

def combmodp(n, r, p):
	ans = 1
	while r > 0:
		ans = ans * comb(n % p, r % p) % p
		if ans == 0:
			break
		(n, r) = (n // p, r // p)
	return ans
combtbl = dict()

def comb(n, r, combtbl=combtbl):
	r = min(r, n - r)
	if r < 0:
		return 0
	ans = combtbl.get((n, r), None)
	if ans is not None:
		return ans
	ans = 1
	for i in range(r):
		ans = ans * (n - i) // (i + 1)
	combtbl[n, r] = ans
	return ans

def readints():
	return map(int, input().split())
main()


from math import factorial
_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def factors(M):
	return [p for p in _primes if M % p == 0]

def digits(n, p):
	while n:
		yield (n % p)
		n //= p

def inverse(n, p):
	return pow(n, p - 2, p)

def choose(n, k):
	if n == k == 0:
		return 1
	if n < k or n == 0:
		return 0
	k = min(k, n - k)
	if k == n or k == 0:
		return 1
	result = 1
	for n in range(n, n - k, -1):
		result *= n
	for d in range(1, k + 1):
		result //= d
	return result

def chinese_remainder(congruences, primes, M):
	total = 0
	for (a, p) in zip(congruences, primes):
		m = M // p
		total += a * inverse(m, p) * m
	return total % M

def chooseMod(n, k, M):
	if n == k == 0:
		return 1
	if n < k or n == 0:
		return 0
	k = min(k, n - k)
	if k == n or k == 0:
		return 1
	primes = factors(M)
	congruences = [0] * len(primes)
	for (i, p) in enumerate(primes):
		prod = 1
		for (ni, ki) in zip(digits(n, p), digits(k, p)):
			prod *= choose(ni, ki)
			if prod == 0:
				break
		congruences[i] = prod
	return chinese_remainder(congruences, primes, M)
cases = int(input())
for _ in range(cases):
	(n, k, M) = [int(x) for x in input().split()]
	print(chooseMod(n, k, M))


MAX_PRIME = 47

def primesTo(n):
	potential = [0, 0] + [1] * (n - 1)
	for p in range(2, int(n ** 0.5) + 1):
		if potential[p]:
			for pq in range(2 * p, n + 1, p):
				potential[pq] = 0
	return [p for p in range(n + 1) if potential[p]]
PRIMES = primesTo(MAX_PRIME)

def nCrTo(MAX):
	savednCr = [[1] + [0] * MAX for n in range(MAX + 1)]
	for n in range(1, MAX + 1):
		for r in range(1, MAX + 1):
			savednCr[n][r] = savednCr[n - 1][r] + savednCr[n - 1][r - 1]
	savednCrp = [[[None] + [savednCr[n][r] % p for p in range(1, MAX + 1)] for r in range(MAX + 1)] for n in range(MAX + 1)]
	return savednCrp
savednCrp = nCrTo(MAX_PRIME)

def nCr(n, r):
	if r > n:
		return 0
	return n * nCr(n - 1, r - 1) // r if r and n else 1

def nCrMODP(n, r, p):
	prod = 1
	while n:
		prod *= savednCrp[n % p][r % p][p]
		n //= p
		r //= p
	return prod % p

def ncrMODM(n, r, m):
	pmods = {p: nCrMODP(n, r, p) for p in PRIMES if not m % p}
	total = 0
	for p in pmods:
		mp = m // p
		(r, s) = bezout(p, mp)
		e = s * mp
		total += pmods[p] * e
	return total % m

def bezout(a, b):
	(s, old_s) = (0, 1)
	(t, old_t) = (1, 0)
	(r, old_r) = (b, a)
	while r != 0:
		q = old_r // r
		(old_r, r) = (r, old_r - q * r)
		(old_s, s) = (s, old_s - q * s)
		(old_t, t) = (t, old_t - q * t)
	return (old_s, old_t)
num_cases = int(input())
for case in range(num_cases):
	(N, R, M) = map(int, input().split())
	print(ncrMODM(N, R, M))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


from math import sqrt, factorial
from functools import reduce

def factorize(n):
	if n < -1:
		return [(-1, 1)] + factorize(-n)
	elif n == -1:
		return [(-1, 1)]
	elif n == 0:
		return [(0, 1)]
	elif n == 1:
		return [(1, 1)]
	else:

		def potential_primes():
			base_primes = (2, 3, 5)
			for base_prime in base_primes:
				yield base_prime
			base_primes = (7, 11, 13, 17, 19, 23, 29, 31)
			prime_group = 0
			while True:
				for base_prime in base_primes:
					yield (prime_group + base_prime)
				prime_group += 30
		factors = []
		sqrtn = sqrt(n)
		for divisor in potential_primes():
			if divisor > sqrtn:
				break
			power = 0
			while n % divisor == 0:
				n //= divisor
				power += 1
			if power > 0:
				factors.append((divisor, power))
				sqrtn = sqrt(n)
		if n > 1:
			factors.append((n, 1))
		return factors

def Conv(n, p):
	r = []
	(a, b) = divmod(n, p)
	while a > 0:
		r.append(b)
		(a, b) = divmod(a, p)
	r.append(b)
	return r

def Lucas(n, r, m):
	a = 1
	for i in range(len(n)):
		if n[i] >= r[i]:
			a *= int(factorial(n[i]) / (factorial(r[i]) * factorial(n[i] - r[i])))
		else:
			a = 0
	return int(a % m)

def chinese_remainder(n, a):
	sum1 = 0
	prod = int(reduce(lambda a, b: a * b, n))
	for (n_i, a_i) in zip(n, a):
		p = prod // n_i
		sum1 += a_i * mul_inv(p, n_i) * p
	return int(sum1 % prod)

def mul_inv(a, b):
	b0 = b
	(x0, x1) = (0, 1)
	if b == 1:
		return 1
	while a > 1:
		q = a // b
		(a, b) = (b, a % b)
		(x0, x1) = (x1 - q * x0, x0)
	if x1 < 0:
		x1 += b0
	return x1
for _ in range(int(input())):
	(N, R, M) = [int(ns) for ns in input().split()]
	if M < 2:
		print(0)
		continue
	MM = []
	for m in factorize(M):
		MM.append(m[0] ** m[1])
	ans = []
	for m in MM:
		n = Conv(N, m)
		r = Conv(R, m)
		while len(n) > len(r):
			r.append(0)
		ans.append(Lucas(n, r, m))
	print(chinese_remainder(MM, ans))


from functools import reduce
from operator import mul
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
factors = []
factorial = [1] * 48
for n in range(1, 48):
	factorial[n] = n * factorial[n - 1]

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def digits(num, base):
	result = []
	while num:
		(num, digit) = divmod(num, base)
		result.append(digit)
	return result

def nCr_m(n, r, p):
	if n < r:
		return 0
	return factorial[n] // (factorial[n - r] * factorial[r]) % p

def nCr(n, r, m):
	answer = 0
	for p in factors:
		nCr_p = reduce(mul, [nCr_m(ni, ri, p) for (ni, ri) in zip(digits(n, p), digits(r, p))]) % p
		coeff = m // p
		answer += coeff * mod_inv(coeff % p, p) * nCr_p
	return answer % m
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	factors = [p for p in primes if m % p == 0]
	print(nCr(n, r, m))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
No_Pr = 15
MAXN = 50
nCr = [[[0 for x in range(MAXN)] for x in range(MAXN)] for i in range(No_Pr)]

def Calculate_nCr():
	for i in range(0, 15):
		nCr[i][0][0] = 1
		nCr[i][1][0] = 1
		nCr[i][1][1] = 1
		for j in range(2, MAXN):
			nCr[i][j][0] = 1
			for k in range(1, j + 1):
				nCr[i][j][k] = (nCr[i][j - 1][k] + nCr[i][j - 1][k - 1]) % primes[i]

class struct:

	def __init__(self):
		self.a = 0
		self.b = 0

def solve():
	s = input()
	(N, R, M) = s.strip().split(' ')
	N = int(N)
	R = int(R)
	M = int(M)
	v = []
	for i in range(0, No_Pr):
		if M % primes[i] == 0:
			if i > 5:
				j = 16
			else:
				j = 31
			ans_p = 1
			temp_N = N
			temp_R = R
			while j >= 0:
				x = primes[i] ** j
				n = temp_N // x
				d = temp_R // x
				if d > n:
					ans_p = 0
					break
				ans_p = ans_p * nCr[i][n][d]
				ans_p %= primes[i]
				temp_N -= n * x
				temp_R -= d * x
				j -= 1
			s = struct()
			s.a = primes[i]
			s.b = ans_p
			v.append(s)
	siz = len(v)
	B = int(1)
	for i in range(0, siz):
		B = B * v[i].a
	ans = int(0)
	for i in range(siz):
		x = B // v[i].a
		ans = (ans + v[i].b * x * pow(x, v[i].a - 2, v[i].a)) % B
	print(ans)

def main():
	Calculate_nCr()
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


def prime_factors(n):
	factors = []
	d = 2
	while n > 1:
		while n % d == 0:
			factors.append(d)
			n /= d
		d = d + 1
	return factors

def n_as_base_b(n, b):
	q = n
	k = 0
	a = []
	i = len(str(n))
	while q != 0:
		a.reverse()
		a.append(q % b)
		a.reverse()
		q = q // b
		k += 1
	return a
import operator as op
import functools

def ncr(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
import math
T = input().strip()
a = []
for a_i in range(int(T)):
	a_t = [int(a_temp) for a_temp in input().strip().split(' ')]
	a.append(a_t)
for line in a:
	N = line[0]
	R = line[1]
	M = line[2]
	factors = prime_factors(M)
	comb = []
	for Mi in factors:
		Ni = n_as_base_b(N, Mi)
		Ri = n_as_base_b(R, Mi)
		temp = 1
		for k in range(0, len(Ri)):
			temp *= ncr(int(Ni[-k - 1]), int(Ri[-k - 1]))
		comb.append(temp)
	sol = 0
	for k in range(0, len(comb)):
		Mj = int(M / factors[k])
		Mjinv = pow(Mj, factors[k] - 2, factors[k])
		sol += comb[k] * Mj * Mjinv
		sol = int(sol % M)
	print(sol)


from math import factorial as fac

def factorize(n):
	factors = []
	rest = n
	for i in range(2, 50):
		if rest % i == 0:
			factors.append(i)
			rest //= i
	return factors

def binomial(x, y):
	if x == y:
		return 1
	try:
		binom = fac(x) // fac(y) // fac(x - y)
	except ValueError:
		binom = 0
	return binom

def get_digits(n, p):
	digits = []
	while n > 0:
		digits.append(n % p)
		n //= p
	return digits

def binom_mod(n, k, p):
	n_digits = get_digits(n, p)
	k_digits = get_digits(k, p)
	diff = len(n_digits) - len(k_digits)
	if diff < 0:
		n_digits += [0] * abs(diff)
	elif diff > 0:
		k_digits += [0] * diff
	prod = 1
	for (ni, ki) in zip(n_digits, k_digits):
		prod = prod * binomial(ni, ki) % p
	return prod

def chinese_remainder(rests):
	sum = 0
	prod = 1
	for (n_i, a_i) in rests:
		prod *= n_i
	for (n_i, a_i) in rests:
		p = prod // n_i
		sum += a_i * mul_inv(p, n_i) * p
	return sum % prod

def mul_inv(a, b):
	b0 = b
	(x0, x1) = (0, 1)
	if b == 1:
		return 1
	while a > 1:
		q = a // b
		(a, b) = (b, a % b)
		(x0, x1) = (x1 - q * x0, x0)
	if x1 < 0:
		x1 += b0
	return x1

def solve(N, R, M):
	factors = factorize(M)
	rests = [(p, binom_mod(N, R, p)) for p in factors]
	print(chinese_remainder(rests))

def process():
	T = int(input())
	for i in range(T):
		(N, R, M) = map(int, input().split())
		solve(N, R, M)
process()


primes50 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base(x, m):
	l = list()
	while x > 0:
		l.append(x % m)
		x //= m
	return l

def modpow(x, e, m):
	acc = 1
	curpow = x
	while e > 0:
		if e & 1:
			acc = acc * curpow % m
		curpow = curpow ** 2 % m
		e >>= 1
	return acc

def flt(a, p):
	return modpow(a, p - 2, p)

def modfac(x, m):
	acc = 1
	for i in range(2, x + 1):
		acc = acc * i % m
	return acc

def modchoose(n, r, p):
	return modfac(n, p) * flt(modfac(r, p), p) * flt(modfac(n - r, p), p) % p

def lucas(N, R, mi):
	Ni = base(N, mi)
	Ri = base(R, mi)
	coeffs = zip(Ni, Ri)
	acc = 1
	for (ni, ri) in coeffs:
		if ni < ri:
			acc = 0
			break
		else:
			acc = acc * modchoose(ni, ri, mi) % mi
	return acc

def crt(A, P, M):
	Ni = [M // pi for pi in P]
	return sum([ai * ni * flt(ni, pi) for (ai, ni, pi) in zip(A, Ni, P)]) % M
for _ in range(int(input())):
	(N, R, M) = map(int, input().strip().split())
	Mi = [p for p in primes50 if M % p == 0]
	Ai = [lucas(N, R, m) for m in Mi]
	print(crt(Ai, Mi, M))


def getPrimesUnder(n):
	if n < 3:
		return
	n2 = n >> 1
	yield 2
	Ns = [True] * n2
	(Ns[0], i) = (False, 1)
	while i < n2:
		if Ns[i]:
			p = (i << 1) + 1
			if p * p > n:
				break
			yield p
			for m in range(i * (i + 1) << 1, n2, p):
				Ns[m] = False
		i += 1
	while i < n2:
		if Ns[i]:
			yield ((i << 1) + 1)
		i += 1
Ps = list(getPrimesUnder(50))

def factorize(n):
	F = []
	for p in Ps:
		if p * p > n:
			break
		count = 0
		(d, r) = divmod(n, p)
		while r == 0:
			n = d
			(d, r) = divmod(n, p)
			count += 1
		if count > 0:
			F.append((p, count))
	if n > 1:
		F.append((n, 1))
	return F

def getInvMod(m, n=None):
	if not n:
		n = m
	Inv = [None, 1]
	for i in range(2, n):
		Inv.append(-(m // i) * Inv[m % i] % m)
	return Inv
invMod = {p: getInvMod(p) for p in Ps}

def CRT(R):
	N = 1
	for (r, n) in R:
		N *= n
	S = 0
	for (r, n) in R:
		S += r * N // n * invMod[n][N // n % n]
	return S % N

def C(r, n):
	if r > n // 2:
		return C(n - r, n)
	if r < 0:
		return 0
	(c, i) = (1, 0)
	for i in range(r):
		c = c * (n - i) // (i + 1)
	return c

def Cmod(r, n, m):
	c = 1
	while r > 0:
		(r, rm) = divmod(r, m)
		(n, nm) = divmod(n, m)
		c *= C(rm, nm)
		c %= m
	return c
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(CRT([(Cmod(r, n, p), p) for (p, e) in factorize(m)]))


def read_ints():
	return tuple([int(x) for x in input().split()])

def modinv(n, p):
	if p == 2:
		return n & 1
	return pow(n, p - 2, p)

def pfact(n, p):
	f = 1
	for i in range(1, n + 1):
		f = f * i % p
	return f

def pcomb(m, n, p):
	if m < n:
		return 0
	if m == n:
		return 1
	num = pfact(m, p)
	den = pfact(n, p) * pfact(m - n, p) % p
	return num * modinv(den, p) % p

def lucas(m, n, p):
	comb = 1
	while m > 0 or n > 0:
		comb = comb * pcomb(m % p, n % p, p) % p
		m //= p
		n //= p
	return comb
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
T = int(input())
for case in range(T):
	(N, R, M) = read_ints()
	x = 0
	for p in primes:
		if M % p == 0:
			n = M // p
			x += lucas(N, R, p) * n * modinv(n, p)
	print(x % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
factorial = [1]
for i in range(1, primes[-1]):
	factorial.append(factorial[-1] * i)
factorial = tuple(factorial)
inv_factorial = {p: tuple((pow(x, p - 2, p) for x in factorial[:p])) for p in primes}
prime_factors = lambda x: tuple((p for p in primes if not x % p))

def base(x, p):
	res = []
	while x:
		res.append(x % p)
		x //= p
	return res

def chinese_remainder(alist, plist, m):
	res = 0
	for (a, p) in zip(alist, plist):
		res = (res + a * pow(m // p, p - 1, m)) % m
	return res

def choose_mod(n, r, p):
	res = 1
	for (nm, rm) in zip(base(n, p), base(r, p)):
		if nm < rm:
			return 0
		res = res * factorial[nm] * inv_factorial[p][rm] * inv_factorial[p][nm - rm] % p
	return res
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	plist = prime_factors(m)
	print(chinese_remainder((choose_mod(n, r, p) for p in plist), plist, m))


from math import factorial

def chinese(A, P):
	N = 1
	for p in P:
		N *= p
	Y = [0 for p in P]
	for (j, p) in enumerate(P):
		Nj = N // p
		(AA, BB) = (Nj, p)
		(a, b) = (Nj, p)
		(s0, s1, t0, t1) = (1, 0, 0, 1)
		while b:
			(a, q, b) = (b, a // b, a % b)
			(s0, s1) = (s1, s0 - q * s1)
			(t0, t1) = (t1, t0 - q * t1)
		if s0 <= 0:
			s0 += BB // a
			t0 -= AA // a
		yj = s0
		A[j] *= yj * Nj
	return (sum(A) % N, N)

def comb(n, k):
	c = 1
	for i in range(n, n - k, -1):
		c *= i
	return c // factorial(k)

def factorise(n):
	P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
	A = []
	for p in P:
		if n % p == 0:
			n //= p
			A.append(p)
	return A

def prime_base(n, p):
	A = []
	while n > 0:
		A.append(n % p)
		n //= p
	return list(reversed(A))
T = int(input())
for t in range(T):
	(N, R, M) = [int(x) for x in input().split()]
	m_a = factorise(M)
	K = [1 for r in m_a]
	for (i, p) in enumerate(m_a):
		N_a = prime_base(N, p)
		R_a = prime_base(R, p)
		if len(R_a) < len(N_a):
			B = [0] * (len(N_a) - len(R_a))
			B.extend(R_a)
			R_a = B
		s = 1
		for (j, n) in enumerate(N_a):
			l = comb(n, R_a[j])
			s *= l
		K[i] = s
	print(chinese(K, m_a)[0])


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


from math import factorial as f
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def megasplit(m):
	i = -1
	res = []
	while m != 1:
		if m % primes[i] != 0:
			i -= 1
		else:
			res.append(primes[i])
			m //= primes[i]
			i = -1
	return res

def gcdex(a, p):
	n = p
	b = a
	(x0, x1) = (1, 0)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
	return x0 % p

def comb(n, m):
	if m > n:
		return 0
	return f(n) // f(m) // f(n - m)

def perevod(n, m, osn):
	c_n = n
	c_m = m
	k = 1
	res_n = []
	res_m = []
	while osn ** (k - 1) <= n:
		res_n.insert(0, c_n % osn)
		res_m.insert(0, c_m % osn)
		c_n //= osn
		c_m //= osn
		k += 1
	return (res_n, res_m)

def lucas(n, m, p):
	(n_p, m_p) = perevod(n, m, p)
	i = 0
	res = 1
	while i < len(n_p):
		res *= comb(n_p[i], m_p[i])
		i += 1
	return res

def china(n, m, p):
	A = megasplit(p)
	R = []
	for i in A:
		R.append(lucas(n, m, i) % i)
	x = 0
	i = 0
	while i < len(A):
		p_i = p // A[i]
		p_i_1 = gcdex(p_i % A[i], A[i])
		x += R[i] * p_i * p_i_1
		i += 1
	return x % p
T = int(input())
for i in range(T):
	(n, r, m) = (int(j) for j in input().split())
	print(china(n, r, m))


from functools import reduce

def main():
	t = int(input())
	for _ in range(t):
		(n, r, m) = map(int, input().split())
		if m > 1:
			print(nCrExtended(n, r, m))
		else:
			print(0)

def nCrExtended(n, r, m):
	(primes, powers) = prime_factorisation(m)
	mods = [pow(a, p, 0) for (a, p) in zip(primes, powers)]
	a = [nCr(n, r, x) for x in mods]
	ans = chinese_remainder(a, mods)
	return ans

def prime_factorisation(n):
	primes = []
	powers = []
	pos = -1
	prime = 2
	while n > 1:
		if n % prime == 0:
			pos += 1
			primes.append(prime)
			powers.append(0)
			while n % prime == 0:
				powers[pos] += 1
				n /= prime
		prime += 1
	return (primes, powers)

def pow(a, b, m):
	(x, y) = (1, a)
	while b > 0:
		if b % 2 == 1:
			x = x * y
			if m > 0 and x > m:
				x %= m
		y = y * y
		if m > 0 and y > m:
			y %= m
		b = int(b / 2)
	return x

def nCr(n, r, p):
	if r == 0:
		return 1
	ni = n % p
	ri = r % p
	val1 = nCr(int(n / p), int(r / p), p)
	val2 = nCrModpDP(ni, ri, p)
	return val1 * val2 % p

def nCrModpDP(n, r, p):
	c = [0] * (r + 1)
	c[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, r), 0, -1):
			c[j] = (c[j] + c[j - 1]) % p
	return c[r]

def chinese_remainder(a, m):
	s = 0
	prod = reduce(lambda a, b: a * b, m)
	for (a_i, m_i) in zip(a, m):
		p = int(prod / m_i)
		s += a_i * mul_inv(p, m_i) * p
	return s % prod

def mul_inv(a, b):
	b0 = b
	(x0, x1) = (0, 1)
	if b == 1:
		return 1
	while a > 1:
		q = int(a / b)
		(a, b) = (b, a % b)
		(x0, x1) = (x1 - q * x0, x0)
	if x1 < 0:
		x1 += b0
	return x1
main()


def choose(n, r):
	if 0 <= r <= n:
		a = 1
		b = 1
		for t in range(min(r, n - r)):
			a *= n - t
			b *= t + 1
		return a // b
	else:
		return 0

def convert(x, b):
	lst = []
	while x > 0:
		(q, r) = divmod(x, b)
		lst.append(r)
		x = q
	return lst

def chinese_rem(prod, rems, mods):
	res = 0
	for (r, p) in zip(rems, mods):
		n = prod // p
		res += n * r * pow(n, p - 2, p)
		res %= prod
	return res
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}
for _ in range(int(input())):
	(n, r, m) = [int(a) for a in input().split()]
	(rems, mods) = ([], [])
	for p in filter(lambda x: m % x == 0, primes):
		nlst = convert(n, p)
		rlst = convert(r, p)
		rlst += [0] * (len(nlst) - len(rlst))
		res = 1
		for (i, j) in zip(nlst, rlst):
			res *= choose(i, j)
			res %= p
		rems.append(res)
		mods.append(p)
	print(chinese_rem(m, rems, mods))


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
from collections import Counter
from functools import reduce

def fact(n):
	ans = []
	for i in primes:
		if n % i == 0:
			n = n // i
			ans.append(i)
	return ans

def primefact(n):
	a = []
	if n < 2:
		return []
	while ~n & 1:
		a.append(2)
		n //= 2
		if n == 1:
			return a
	while n % 3 == 0:
		a.append(3)
		n //= 3
		if n == 1:
			return a
	d = 5
	while d * d <= n:
		while n % d == 0:
			a.append(d)
			n //= d
			if n == 1:
				return a
		d += 2
		while n % d == 0:
			a.append(d)
			n //= d
			if n == 1:
				return a
		d += 4
	a.append(n)
	return a

def base(n, p):
	a = []
	while n > 0:
		(n, r) = divmod(n, p)
		a.append(r)
	return a

def C(n, r):
	if n < r:
		return 0
	k = min(r, n - r)
	a = Counter()
	ans = 1
	for i in range(n - k + 1, n + 1):
		a += Counter(primefact(i))
	for i in range(1, k + 1):
		a -= Counter(primefact(i))
	for i in a:
		ans = ans * pow(i, a[i])
	return ans

def Cmodp(n, r, p):
	na = base(n, p)
	ra = base(r, p)
	ra += [0] * (len(na) - len(ra))
	c = list(map(C, na, ra))
	if len(c) == 1:
		return c[0] % p
	return reduce(lambda x, y: x % p * (y % p) % p, c)
invmod = lambda i, p: pow(i, p - 2, p)

def solve(n, r, m):
	factors = fact(m)
	a = list(map(lambda i: Cmodp(n, r, i), factors))
	z = list(map(lambda i: m // i, factors))
	y = list(map(invmod, z, factors))
	w = list(map(lambda x, y: x % m * (y % m) % m, z, y))
	s = 0
	for (i, j) in zip(a, w):
		s += i * j % m
		s %= m
	return s
for _ in range(int(input())):
	(n, r, m) = [int(x) for x in input().split()]
	if m == 1:
		print(0)
		continue
	print(solve(n, r, m))


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def factorize(n, primes):
	ret = []
	for p in primes:
		if n % p == 0:
			ret.append(p)
	return ret

def p_ary(n, p):
	ret = []
	while n > 0:
		ret.append(n % p)
		n //= p
	return ret

def binom_mod(n, k, p):
	if k > n:
		return 0
	if n == 0:
		return 1
	if k < n / 2:
		k = n - k
	ret = 1
	for i in range(k + 1, n + 1):
		ret *= i
	for i in range(1, n - k + 1):
		ret //= i
	return ret % p

def inverse(m, n):
	if n == 1:
		return [0, 1]
	a = inverse(n, m % n)
	return [a[1], a[0] - a[1] * (m // n)]

def solve_CRT(remainders, n, divisors):
	l = len(divisors)
	ret = 0
	for i in range(l):
		quotient = n // divisors[i]
		a = inverse(quotient, divisors[i])
		ret = (ret + a[0] * quotient * remainders[i]) % n
	return ret
t = int(input())
while t > 0:
	t -= 1
	(n, r, m) = [int(x) for x in input().split()]
	divisors = factorize(m, primes)
	remainders = []
	for p in divisors:
		np = p_ary(n, p)
		rp = p_ary(r, p)
		tmp = 1
		for i in range(len(rp)):
			tmp = tmp * binom_mod(np[i], rp[i], p) % p
		remainders.append(tmp)
	print(solve_CRT(remainders, m, divisors))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


from functools import reduce
from operator import mul
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def fact_mod(n, p):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i % p
	return ans

def egcd(a, b):
	if a == 0:
		return (0, 1)
	(x, y) = egcd(b % a, a)
	return (y - b // a * x, x)

def binom_small(n, m, p):
	if n < m:
		return 0
	return fact_mod(n, p) * pow(fact_mod(m, p) * fact_mod(n - m, p), p - 2, p) % p

def binom_prime(n, m, p):
	ans = 1
	while n > 0 or m > 0:
		ans = ans * binom_small(n % p, m % p, p) % p
		n //= p
		m //= p
	return ans

def binom_mod(n, m, a):
	ps = [p for p in PRIMES if a % p == 0]
	N = reduce(mul, ps, 1)
	res = 0
	for p in ps:
		(s, t) = egcd(p, N // p)
		res = (res + binom_prime(n, m, p) * t * (N // p)) % a
	return res
T = int(input())
for t in range(T):
	(N, R, M) = map(int, input().split())
	print(binom_mod(N, R, M))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


from math import factorial

def comb(n, r):
	if 0 > r or r > n:
		return 0
	return factorial(n) // factorial(n - r) // factorial(r)

def pcomb(n, r, p):
	res = 1
	while n:
		res = res * comb(n % p, r % p) % p
		n //= p
		r //= p
	return res

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def factorize(n):
	res = []
	if n % 2 == 0:
		power = 0
		while n % 2 == 0:
			power += 1
			n //= 2
		res.append((2, power))
	i = 3
	while i * i <= n:
		if n % i == 0:
			power = 0
			while n % i == 0:
				power += 1
				n //= i
			res.append((i, power))
		i += 2
	if n > 1:
		res.append((n, 1))
	return res

def chinese(A, N):
	tot = 1
	for n in N:
		tot *= n
	N2 = [tot // n for n in N]
	return sum((a * n2 * modinv(n2, n) for (a, n2, n) in zip(A, N2, N))) % tot
for _ in range(int(input())):
	(n, r, m) = [int(x) for x in input().split()]
	ps = []
	rems = []
	for (p, _) in factorize(m):
		ps.append(p)
		rems.append(pcomb(n, r, p))
	print(chinese(rems, ps))


def nchoosek(n, k):
	a = 1
	if n < 0 or k < 0 or n < k:
		return 0
	for i in range(0, k):
		a *= n - i
	for j in range(1, k + 1):
		a //= j
	return a

def powerize(n, k):
	L = []
	while n >= 1:
		L.append(n % k)
		n //= k
	if not L:
		L = [0]
	return L

def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	for p in PL:
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def euler_totient_with_factors(n, factors):
	for ar_elet in factors:
		n //= ar_elet[0]
		n *= ar_elet[0] - 1
	return n

def gcd_matrix_coefficients(a, b):
	M = [[1, 0, a], [0, 1, b]]
	if a > 0 and b > 0:
		while M[0][2] != 0 and M[1][2] != 0:
			if M[0][2] > M[1][2]:
				multiple = M[0][2] // M[1][2]
				for i in range(0, 3):
					M[0][i] -= multiple * M[1][i]
			elif M[0][2] < M[1][2]:
				multiple = M[1][2] // M[0][2]
				for i in range(0, 3):
					M[1][i] -= multiple * M[0][i]
			elif M[0][2] == M[1][2]:
				return M[0][2]
		if M[0][2] == 0:
			return (M[1][0], M[1][1])
		else:
			return (M[0][0], M[0][1])
	elif a != 0 and b != 0:
		return gcd_matrix(abs(a), abs(b))
	else:
		return (0, 0)

def gcd_matrix(a, b):
	M = [[1, 0, a], [0, 1, b]]
	if a > 0 and b > 0:
		while M[0][2] != 0 and M[1][2] != 0:
			if M[0][2] > M[1][2]:
				multiple = M[0][2] // M[1][2]
				for i in range(0, 3):
					M[0][i] -= multiple * M[1][i]
			elif M[0][2] < M[1][2]:
				multiple = M[1][2] // M[0][2]
				for i in range(0, 3):
					M[1][i] -= multiple * M[0][i]
			elif M[0][2] == M[1][2]:
				return M[0][2]
		if M[0][2] == 0:
			return M[1][2]
		else:
			return M[0][2]
	elif a != 0 and b != 0:
		return gcd_matrix(abs(a), abs(b))
	else:
		return 0

def chinese_remainder_theorem(x_list, mod_list):
	current_mod = mod_list[0]
	current_x = x_list[0]
	for i in range(1, len(x_list)):
		(a, b) = gcd_matrix_coefficients(current_mod, mod_list[i])
		current_x = current_x * b * mod_list[i] + x_list[i] * a * current_mod
		current_mod *= mod_list[i]
	return current_x % current_mod

def lucas_nchoosek(N, K, P):
	powers_of_N = powerize(N, P)
	powers_of_K = powerize(K, P)
	result = 1
	for i in range(0, len(powers_of_K)):
		result *= nchoosek(powers_of_N[i], powers_of_K[i])
		result %= P
	return result
PL = prime_list(100000)
T = int(input())
for _ in range(T):
	(N, R, M) = [int(a) for a in input().split()]
	factors_of_M = factor(M, PL)
	if M != 1:
		X = [lucas_nchoosek(N, R, f[0]) for f in factors_of_M]
		Mod_list = [f[0] for f in factors_of_M]
		print(chinese_remainder_theorem(X, Mod_list))
	else:
		print(0)


import sys
from itertools import zip_longest

def rcoeff_gen(n, p):
	if n == 0:
		yield 0
	while n:
		yield (n % p)
		n //= p

def pf_gen(m):
	ff = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
	for f in ff:
		if f > m:
			break
		if m % f == 0:
			yield f
			m //= f
	if m != 1:
		yield m

def inv_mod(n, p):
	return pow(n, p - 2, p)

def bc_mod(m, n, p):

	def coeff(m, n, p):
		rval = 1
		(u, v) = (m, 1)
		while v != n + 1:
			rval *= u
			rval %= p
			rval *= inv_mod(v, p)
			rval %= p
			u -= 1
			v += 1
		return rval
	rval = 1
	for (cm, cn) in zip_longest(rcoeff_gen(m, p), rcoeff_gen(n, p), fillvalue=0):
		if cm < cn:
			return 0
		rval *= coeff(cm, cn, p)
	return rval

def solve_equation(ee):
	if not ee:
		return 0
	if len(ee) == 0:
		(_, a) = ee[0]
		return a
	N = 1
	for (n, _) in ee:
		N *= n
	(yy, zz) = ([], [])
	for (n, _) in ee:
		y = N // n
		yy.append(y)
		z = inv_mod(y, n)
		zz.append(z)
	x = 0
	for ((n, a), y, z) in zip(ee, yy, zz):
		print('n=%d a=%d y=%d z=%d' % (n, a, y, z), file=sys.stderr)
		x += a * y * z
	return x % N

def solve(n, r, m):
	print('n=%d r=%d m=%d' % (n, r, m), file=sys.stderr)
	ff = tuple(pf_gen(m))
	ee = []
	for f in ff:
		c = bc_mod(n, r, f)
		ee.append((f, c))
		print('f=%d c=%d' % (f, c), file=sys.stderr)
	return solve_equation(ee)
t = int(input())
for _ in range(t):
	(n, r, m) = map(int, input().split())
	print(solve(n, r, m))


def ntb(n, r, d, f):
	if n == 0:
		return 1
	(x, y) = (n % d, r % d)
	if x < y:
		return 0
	return ntb(n // d, r // d, d, f) * f[x] % d * pow(f[y] * f[x - y], d - 2, d) % d

def remain(n, r, m, d):
	fact = [1] * 50
	for i in range(1, 50):
		fact[i] = i * fact[i - 1] % d
	a = m // d
	return ntb(n, r, d, fact) * a % m * pow(a, d - 2, d) % m
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
for _ in range(int(input())):
	(n, r, m) = list(map(int, input().split()))
	ans = 0
	for d in p:
		if m % d == 0:
			ans = (ans + remain(n, r, m, d)) % m
	print(ans)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


from math import sqrt

def primes(n):
	primes = []
	for i in range(2, n):
		b = True
		for j in range(2, int(sqrt(i) + 1)):
			if i % j == 0:
				b = False
				break
		if b:
			primes.append(i)
	return primes

def binomialModulo(n, k, p):
	if k > n:
		return 0
	ret = 1
	counter = 0
	for i in range(max(n - k, k) + 1, n + 1):
		t = i
		while t % p == 0:
			counter += 1
			t = int(t / p)
		else:
			ret = ret * t % p
	for i in range(2, min(n - k, k) + 1):
		t = i
		while t % p == 0:
			counter -= 1
			t = int(t / p)
		else:
			ret = ret * pow(t, p - 2, p) % p
	if counter > 0:
		return 0
	return ret

def extended_euclidean(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = extended_euclidean(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = extended_euclidean(a, m)
	return x % m

def crt(m, x):
	if len(x) < 2:
		return x[0]
	while True:
		temp1 = modinv(m[1], m[0]) * x[0] * m[1] + modinv(m[0], m[1]) * x[1] * m[0]
		temp2 = m[0] * m[1]
		x.remove(x[0])
		x.remove(x[0])
		x = [temp1 % temp2] + x
		m.remove(m[0])
		m.remove(m[0])
		m = [temp2] + m
		if len(x) == 1:
			break
	return x[0]
t = int(input().rstrip())
primes = primes(50)
for i in range(t):
	(n, r, m) = list(map(int, input().rstrip().split()))
	if m > 1:
		X = []
		Y = []
		for prime in primes:
			if m % prime == 0:
				t_n = n
				t_r = r
				tmp = 1
				while t_n > 0:
					tmp = tmp * binomialModulo(t_n % prime, t_r % prime, prime) % prime
					t_n = int(t_n / prime)
					t_r = int(t_r / prime)
				X.append(prime)
				Y.append(tmp)
		print(crt(X, Y))
	else:
		print(0)


import math

def nCk(n, k):
	if n < k:
		return 0
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def decompose(n):
	facteurs = {}
	i = 2
	while i * i <= n:
		while n % i == 0:
			n = n // i
			facteurs[i] = facteurs.get(i, 0) + 1
		if i >= 3:
			i += 2
		else:
			i += 1
	if n > 1:
		facteurs[n] = facteurs.get(n, 0) + 1
	return facteurs

def base(x, b):
	d = []
	while x != 0:
		(x, r) = divmod(x, b)
		d.append(r)
	return d

def lucas(m, n, p):
	M = base(m, p)
	N = base(n, p)
	C = 1
	for (mi, ni) in zip(M, N):
		C *= nCk(mi, ni) % p
		C %= p
	return C

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def nCk_mod(n, r, m):
	if m < 2:
		return 0
	p = decompose(m)
	assert set(p.values()) == set({1})
	p = list(p.keys())
	x = 0
	for pi in p:
		ai = lucas(n, r, pi)
		(_, _, v) = egcd(pi, m // pi)
		x += ai * v * (m // pi)
	return x % m
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(nCk_mod(n, r, m))


import sys, random
from math import sqrt

def fact_p_count(n, p):
	n //= p
	m = n
	while n >= p:
		n //= p
		m += n
	return m

def mod_inverse(n, s=0):
	if s == 0:
		s = n - 1
	inv = [0] * (s + 1)
	inv[1] = 1
	for i in range(2, s + 1):
		inv[i] = inv[n % i] * (n - n // i) % n
	return inv

def pollard_rho(N, rand=random.randint):
	if N & 1 == 0:
		return 2
	(y, c, m) = (rand(1, N - 1), rand(1, N - 1), 250)
	while c == N - 2:
		c = rand(1, N - 1)
	(g, r, q) = (1, 1, 1)
	while g == 1:
		x = y
		for i in range(r):
			y = (y * y + c) % N
		for k in range(0, r, m):
			ys = y
			for _ in range(min(m, r - k)):
				y = (y * y + c) % N
				q = q * (y - x) % N
			g = gcd(q, N)
			if g != 1:
				break
		r <<= 1
	if g == N:
		g = 1
		while g == 1:
			ys = (ys * ys + c) % N
			g = gcd(x - ys, N)
	return g

def factors(n):
	if n <= 1:
		return []
	PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031]
	ret = []
	two = n & -n
	e = two.bit_length() - 1
	if e > 0:
		ret.append((2, e))
		n >>= e
	p_max = int(n ** 0.5)
	for p in PRIMES[1:]:
		if p > p_max:
			break
		(q, r) = divmod(n, p)
		if r:
			continue
		e = 1
		n = q
		while 1:
			(q, r) = divmod(n, p)
			if r:
				break
			e += 1
			n = q
		ret.append((p, e))
		p_max = int(n ** 0.5)
	if n > 1:
		if p_max <= PRIMES[-1] or miller_rabin(n):
			ret.append((int(n), 1))
		else:
			large_primes = []
			threshold = PRIMES[-1] ** 2
			while 1:
				p = pollard_rho(n)
				if not miller_rabin(p):
					continue
				n //= p
				e = 1
				while 1:
					(q, r) = divmod(n, p)
					if r:
						break
					n = q
					e += 1
				large_primes.append((int(p), e))
				if n <= threshold or miller_rabin(n):
					if n > 1:
						large_primes.append((int(n), 1))
					break
			ret += sorted(large_primes)
	return ret

def extgcd(x, y, z=1):
	(q, r) = divmod(x, y)
	if r != 0:
		(x, y) = extgcd(y, r, z)
		return (y, x - y * q)
	else:
		return (0, z)

def binomial_p(n, m, p, facts=[], inv_facts=[]):
	if n < 0 or m < 0 or m > n or (p == 1):
		return 0
	rems_n = []
	rems_m = []
	while n > 0:
		rems_n.append(n % p)
		rems_m.append(m % p)
		n //= p
		m //= p
	if len(facts) == 0:
		size = max(max(rems_n), max(rems_m))
		invs = mod_inverse(p, size)
		facts = [1] * (size + 1)
		inv_facts = [1] * (size + 1)
		for i in range(1, size + 1):
			facts[i] = facts[i - 1] * i % p
			inv_facts[i] = inv_facts[i - 1] * invs[i] % p
	ret = 1
	for (n1, d1) in zip(rems_n, rems_m):
		if n1 < d1:
			ret = 0
			break
		ret = ret * facts[n1] * inv_facts[d1] * inv_facts[n1 - d1] % p
	return ret

def calc_fact_p(n, p, q, facts, fact_p, inv_fact_p):
	if n < p * q:
		return fact_p[n]
	u = n // p
	v = n - u * p
	r = (q + 1) // 2
	mod = p ** q
	phi = (p - 1) * p ** (q - 1)
	ret = fact_p[v]
	beta_numer = u
	for j in range(1, r + 1):
		beta_numer *= (u - j) * (u + j)
	for j in range(1, r + 1):
		beta_denom = (u - j) * (u + j)
		beta_denom *= facts[j + r] * facts[r - j]
		if r - j & 1:
			beta_denom = -beta_denom
		beta = beta_numer * (2 * j) // beta_denom % phi
		ret = ret * pow(fact_p[j * p], beta, mod) % mod
	if p == 2:
		left_mod4 = ((u * p + 1 & 4) >> 1) + 1
		right_mod4 = ret & 3
		if left_mod4 != right_mod4:
			ret = (mod - ret) % mod
	alpha_numer = u
	for j in range(1, q):
		alpha_numer *= u - j
	for j in range(1, q):
		alpha_denom = (u - j) * facts[j] * facts[q - 1 - j]
		if q - 1 - j & 1:
			alpha_denom = -alpha_denom
		alpha = alpha_numer // alpha_denom % phi
		base = fact_p[j * p + v] * inv_fact_p[j * p] * inv_fact_p[v] % mod
		ret = ret * pow(base, alpha, mod) % mod
	return ret

def _binomial_pq_small(n, m, p, q, fact_p, inv_fact_p):
	mod = p ** q
	r = n - m
	ret = 1
	if len(fact_p) == 0:
		required_size = 0
		(n_, m_, r_) = (n, m, r)
		while n_ > 0:
			required_size = max(required_size, n_ % mod)
			required_size = max(required_size, m_ % mod)
			required_size = max(required_size, r_ % mod)
			n_ //= p
			m_ //= p
			r_ //= p
		(fact_p, inv_fact_p) = make_fact_p(p, q, required_size + 1)
	ret = 1
	while n > 0:
		ret = ret * fact_p[n % mod] * inv_fact_p[m % mod] * inv_fact_p[r % mod] % mod
		n //= p
		m //= p
		r //= p
	return ret

def _binomial_pq_large(n, m, p, q, fact_p, inv_fact_p):
	mod = p ** q
	phi = (p - 1) * p ** (q - 1)
	r = n - m
	facts_size = (q + 1 & ~1) + 1
	facts = [1] * facts_size
	for i in range(1, facts_size):
		facts[i] = facts[i - 1] * i
	if len(fact_p) == 0:
		(fact_p, inv_fact_p) = make_fact_p(p, q, p * q)
	ret = 1
	while n > 0:
		n1 = calc_fact_p(n % mod, p, q, facts, fact_p, inv_fact_p) % mod
		d1 = calc_fact_p(m % mod, p, q, facts, fact_p, inv_fact_p) % mod
		d2 = calc_fact_p(r % mod, p, q, facts, fact_p, inv_fact_p) % mod
		ret = ret * n1 * pow(d1 * d2, phi - 1, mod) % mod
		n //= p
		m //= p
		r //= p
	return ret

def binomial_pq(n, m, p, q, fact_p=[], inv_fact_p=[]):
	if n < 0 or m < 0 or m > n or (p == 1):
		return 0
	r = n - m
	e0 = fact_p_count(n, p) - fact_p_count(m, p) - fact_p_count(r, p)
	if e0 >= q:
		return 0
	if q == 1:
		return binomial_p(n, m, p)
	mod = p ** q
	if mod <= 10 ** 4:
		ret = _binomial_pq_small(n, m, p, q, fact_p, inv_fact_p)
	else:
		ret = _binomial_pq_large(n, m, p, q, fact_p, inv_fact_p)
	eq1 = fact_p_count(n // (mod // p), p)
	eq1 -= fact_p_count(m // (mod // p), p)
	eq1 -= fact_p_count(r // (mod // p), p)
	if not (p == 2 and q >= 3) and eq1 & 1 == 1:
		ret = (mod - ret) % mod
	ret = ret * p ** e0 % mod
	return ret

def crt(ps, rems):
	rem = rems[0]
	pro = ps[0]
	for i in range(1, len(rems)):
		(a, b) = extgcd(pro, ps[i])
		rem = (ps[i] * b * rem + pro * a * rems[i]) % (pro * ps[i])
		pro *= ps[i]
	return rem

def binomial_mod(n, m, mod):
	if n < 0 or m < 0 or m > n or (mod == 1):
		return 0
	f = factors(mod)
	rems = []
	ps = []
	for (p, e) in f:
		rems.append(binomial_pq(n, m, p, e))
		ps.append(p ** e)
	return crt(ps, rems)

def solve():
	stdin = sys.stdin
	T = int(stdin.readline())
	mat = [[0, 1], [1, 1]]
	MOD = 10 ** 9 + 7
	for _ in range(T):
		(N, R, M) = map(int, stdin.readline().split())
		print(binomial_mod(N, R, M))
solve()


pr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def pascal(n):
	p = [[1] * (i + 1) for i in range(n)]
	for i in range(n):
		for j in range(1, i):
			p[i][j] = p[i - 1][j - 1] + p[i - 1][j]
	return p
pa = pascal(pr[-1])

def expand(a, p):
	x = []
	while a:
		x.append(a % p)
		a //= p
	return x

def lucas(n, r, p):
	np = expand(n, p)
	rp = expand(r, p)
	z = 1
	for (a, b) in zip(rp, np):
		if b < a:
			return 0
		else:
			z = z * pa[b][a] % p
	return z
from functools import reduce
from operator import mul

def cheese(n, r, m):
	if m == 1:
		return 0
	ms = [p for p in pr if 0 == m % p]
	bs = [lucas(n, r, p) for p in ms]
	prod = reduce(mul, ms)
	gs = [prod // p for p in ms]
	cs = [g * pow(g, p - 2, p) for (g, p) in zip(gs, ms)]
	ans = 0
	for (b, c) in zip(bs, cs):
		ans = (ans + b * c) % m
	return ans
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(cheese(n, r, m))


import os
import sys
import math

def nCk(n, k):
	if n < k:
		return 0
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def decompose(n):
	facteurs = {}
	i = 2
	while i * i <= n:
		while n % i == 0:
			n = n // i
			facteurs[i] = facteurs.get(i, 0) + 1
		if i >= 3:
			i += 2
		else:
			i += 1
	if n > 1:
		facteurs[n] = facteurs.get(n, 0) + 1
	return facteurs

def base(x, b):
	d = []
	while x != 0:
		(x, r) = divmod(x, b)
		d.append(r)
	return d

def lucas(m, n, p):
	M = base(m, p)
	N = base(n, p)
	C = 1
	for (mi, ni) in zip(M, N):
		C *= nCk(mi, ni) % p
		C %= p
	return C

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def nCk_mod(n, r, m):
	if m < 2:
		return 0
	p = decompose(m)
	assert set(p.values()) == set({1})
	p = list(p.keys())
	x = 0
	for pi in p:
		ai = lucas(n, r, pi)
		(_, _, v) = egcd(pi, m // pi)
		x += ai * v * (m // pi)
	return x % m
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(nCk_mod(n, r, m))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


def inv(a, p):
	return pow(a, p - 2, p)

def primeGen():
	q = 2
	D = {}
	while True:
		if q in D:
			for p in D[q]:
				D.setdefault(q + p, []).append(p)
			del D[q]
		else:
			yield q
			D[q * q] = [q]
		q += 1
PG = primeGen()
P = [next(PG)]
while P[-1] < 50:
	P.append(next(PG))
factorials_p = {}
invFactorials_p = {}
for p in P:
	factorials_p[p] = [1, 1]
	invFactorials_p[p] = [1, 1]
	for x in range(2, p):
		factorials_p[p].append(x * factorials_p[p][-1] % p)
		invFactorials_p[p].append(inv(factorials_p[p][-1], p))

def primeFactorize(q):
	if q == 1:
		return {}
	else:
		PF = {}
		(dex, p) = (0, P[0])
		while p * p <= q:
			if q % p:
				(dex, p) = (dex + 1, P[dex + 1])
			else:
				PF[p] = PF.get(p, 0) + 1
				q = q // p
		PF[q] = PF.get(q, 0) + 1
		return PF

def baseRep(a, p):
	BR = []
	while a >= p:
		BR.append(a % p)
		a = a // p
	BR.append(a)
	return BR

def compute_n_choose_r_mod_p(n, r, p):
	(N_p, R_p) = (baseRep(n, p), baseRep(r, p))
	lengthDifference = len(N_p) - len(R_p)
	for _ in range(lengthDifference):
		R_p.append(0)
	if any([R_p[b] > N_p[b] for b in range(len(N_p))]):
		return 0
	else:
		product = 1
		while N_p:
			(nb, rb) = (N_p.pop(), R_p.pop())
			product *= factorials_p[p][nb]
			product *= invFactorials_p[p][rb] * invFactorials_p[p][nb - rb]
			product = product % p
		return product

def chineseRemainder(rems):
	prod = max(rems.keys())
	rem = rems.pop(prod)
	while rems:
		(p, remp) = rems.popitem()
		while rem % p != remp:
			rem += prod
		prod *= p
	return rem

def solve(n, r, m):
	if m == 1:
		return 0
	else:
		M = set(primeFactorize(m).keys())
		rems = {}
		for p in M:
			rems[p] = compute_n_choose_r_mod_p(n, r, p)
		return chineseRemainder(rems)
t = int(input())
for t_itr in range(t):
	(n, r, m) = map(int, input().split())
	print(solve(n, r, m))


import math

def nCk(n, k):
	if n < k:
		return 0
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def decompose(n):
	facteurs = {}
	i = 2
	while i * i <= n:
		while n % i == 0:
			n = n // i
			facteurs[i] = facteurs.get(i, 0) + 1
		if i >= 3:
			i += 2
		else:
			i += 1
	if n > 1:
		facteurs[n] = facteurs.get(n, 0) + 1
	return facteurs

def base(x, b):
	d = []
	while x != 0:
		(x, r) = divmod(x, b)
		d.append(r)
	return d

def lucas(m, n, p):
	M = base(m, p)
	N = base(n, p)
	C = 1
	for (mi, ni) in zip(M, N):
		C *= nCk(mi, ni) % p
		C %= p
	return C

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def nCk_mod(n, r, m):
	if m < 2:
		return 0
	p = decompose(m)
	assert set(p.values()) == set({1})
	p = list(p.keys())
	x = 0
	for pi in p:
		ai = lucas(n, r, pi)
		(_, _, v) = egcd(pi, m // pi)
		x += ai * v * (m // pi)
	return x % m
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(nCk_mod(n, r, m))


from functools import lru_cache

def factor(n):
	if n & 1 == 0:
		n >>= 1
		yield 2
	d = 3
	while d * d <= n:
		if n % d == 0:
			n //= d
			yield d
		d += 2
	if n > 1:
		yield n

@lru_cache(maxsize=None)
def binom(n, p):
	if p > n:
		return 0
	return 1 if p == 0 else n * binom(n - 1, p - 1) // p

def binom_lucas(n, k, p):
	res = 1
	while n > 0 or k > 0:
		(n, a) = divmod(n, p)
		(k, b) = divmod(k, p)
		res = res * binom(a, b) % p
	return res

def bezout(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, u, v) = bezout(b, a % b)
	return (g, v, u - a // b * v)

def rev_chinois(a, p, b, q):
	(_, u, v) = bezout(p, q)
	return (b * u * p + a * v * q) % (p * q)

def main():
	T = int(input())
	for _ in range(T):
		(N, R, M) = map(int, input().split())
		(res, m) = (0, 1)
		for p in factor(M):
			resp = binom_lucas(N, R, p)
			res = rev_chinois(res, m, resp, p)
			m *= p
		print(res)
main()


from math import factorial
_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def factors(M):
	return [p for p in _primes if M % p == 0]

def digits(n, p):
	while n:
		yield (n % p)
		n //= p

def inverse(n, p):
	return pow(n, p - 2, p)

def choose(n, k):
	if n == k == 0:
		return 1
	if n < k or n == 0:
		return 0
	k = min(k, n - k)
	if k == n or k == 0:
		return 1
	result = 1
	for n in range(n, n - k, -1):
		result *= n
	for d in range(1, k + 1):
		result //= d
	return result

def chinese_remainder(congruences, primes, M):
	total = 0
	for (a, p) in zip(congruences, primes):
		m = M // p
		total += a * inverse(m, p) * m
	return total % M

def chooseMod(n, k, M):
	if n == k == 0:
		return 1
	if n < k or n == 0:
		return 0
	k = min(k, n - k)
	if k == n or k == 0:
		return 1
	primes = factors(M)
	congruences = [0] * len(primes)
	for (i, p) in enumerate(primes):
		prod = 1
		for (ni, ki) in zip(digits(n, p), digits(k, p)):
			prod *= choose(ni, ki)
			if prod == 0:
				break
		congruences[i] = prod
	return chinese_remainder(congruences, primes, M)
cases = int(input())
for _ in range(cases):
	(n, k, M) = [int(x) for x in input().split()]
	print(chooseMod(n, k, M))


import math

def nCk(n, k):
	if n < k:
		return 0
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def decompose(n):
	facteurs = {}
	i = 2
	while i * i <= n:
		while n % i == 0:
			n = n // i
			facteurs[i] = facteurs.get(i, 0) + 1
		if i >= 3:
			i += 2
		else:
			i += 1
	if n > 1:
		facteurs[n] = facteurs.get(n, 0) + 1
	return facteurs

def base(x, b):
	d = []
	while x != 0:
		(x, r) = divmod(x, b)
		d.append(r)
	return d

def lucas(m, n, p):
	M = base(m, p)
	N = base(n, p)
	C = 1
	for (mi, ni) in zip(M, N):
		C *= nCk(mi, ni) % p
		C %= p
	return C

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def nCk_mod(n, r, m):
	if m < 2:
		return 0
	p = decompose(m)
	assert set(p.values()) == set({1})
	p = list(p.keys())
	x = 0
	for pi in p:
		ai = lucas(n, r, pi)
		(_, _, v) = egcd(pi, m // pi)
		x += ai * v * (m // pi)
	return x % m
for _ in range(int(input())):
	(n, r, m) = map(int, input().split())
	print(nCk_mod(n, r, m))


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import itertools, sys
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def base_coefficients(n, base):
	coefficients = []
	while n > 0:
		coefficients.append(n % base)
		n //= base
	return coefficients

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def lucas_theorem(n, k, p):
	x = itertools.zip_longest(base_coefficients(n, p), base_coefficients(k, p), fillvalue=0)
	product = 1
	for (n_i, k_i) in x:
		product = product * choose(n_i, k_i) % p
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, R, M) = list(map(int, sys.stdin.readline().split()))
	primes = [p for p in PRIMES if M % p == 0]
	total = 0
	for p in primes:
		total += lucas_theorem(N, R, p) * (M // p) * pow(M // p, p - 2, p) % M
	print(total % M)


import os
import sys
primeslt50 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def primes(m):
	return [x for x in primeslt50 if m % x == 0]

def choose(n, r):
	if n < r or r > n:
		return 0
	if r == 0:
		return 1
	num = 1
	denom = 1
	for i in range(0, r):
		num *= n - i
		denom *= i + 1
	return num // denom

def base_repr(n, p):
	values = []
	while n > 0:
		values.append(n % p)
		n //= p
	return values

def extended_gcd(m, n):
	c = m
	d = n
	ao = b = 1
	a = bo = 0
	while True:
		(q, r) = divmod(c, d)
		if r == 0:
			break
		c = d
		d = r
		t = ao
		ao = a
		a = t - q * a
		t = bo
		bo = b
		b = t - q * b
	return (d, a, b)

def binv(b, p):
	(_, binv, _) = extended_gcd(b, p)
	return binv % p

def solve(n, r, m):
	if m == 1:
		return 0
	pr = primes(m)
	a = []
	for p in pr:
		nb = base_repr(n, p)
		rb = base_repr(r, p)
		value = 1
		for (x, y) in zip(nb, rb):
			value *= choose(x, y)
			value %= p
		a.append(value)
	if len(a) == 1:
		return a[0]
	x = 0
	for (ai, ni) in zip(a, pr):
		Ni = m // ni
		di = binv(Ni, ni)
		x += ai * Ni * di
		x %= m
	return x
t = int(input())
for t_itr in range(t):
	nrm = input().split()
	n = int(nrm[0])
	r = int(nrm[1])
	m = int(nrm[2])
	result = solve(n, r, m)
	print(str(result))