Given 3 integers n, r and m. You task is to calculate ^{n}Cr%m.
Note: m is a square free number and largest prime factor of m <= 50.
 
Example 1:
Input: n = 5, r = 2, m = 98697
Output: 10
Explanation: ^{5}C2 = 5!/(2!*3!) = 10%98697 = 10
Example 2:
Input: n = 3, r = 2, m = 98697
Output: 3
Explanation: ^{3}C2 = 3!/(2!*1!) = 3%98697 = 3
 
Your Task:
You don't need to read or print anything. Your task is to complete the function nCrModM() which takes n, r and m as input parameter and returns nCr modulo m.
 
Expected Time Complexity: O(m + log_{m}n) 
Expected Space Complexity: O(m)
 
Constraints:
1 <= r <= n <= 10^{9}
1 <= m <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Combinatorics

Starter code: #User function Template for python3



class Solution:

	def nCrModM(self, n, r, m):

		# Code here

Solutions:
class Solution:

	def nCrModM(self, n, r, m):

		def leastPrimeFactor(n):
			least_prime = [0] * (n + 1)
			least_prime[1] = 1
			for i in range(2, n + 1):
				if least_prime[i] == 0:
					least_prime[i] = i
					for j in range(2 * i, n + 1, i):
						if least_prime[j] == 0:
							least_prime[j] = i
			return least_prime

		def power(x, y, m):
			if y == 0:
				return 1
			p = power(x, y // 2, m) % m
			p = p * p % m
			if y % 2 == 0:
				return p
			else:
				return x * p % m

		def ncr_kris(n, r, p):
			if n < r:
				return 0
			if r > n - r:
				r = n - r
			num = den = 1
			for i in range(r):
				num = num * (n - i) % p
				den = den * (i + 1) % p
			ans = num * power(den, p - 2, p) % p
			return ans

		def toBaseB(N, B):
			digits = []
			while N > 0:
				digits.insert(0, N % B)
				N = N // B
			return digits

		def nCrModp_Lucas(n, r, p):
			m = toBaseB(n, p)
			n = toBaseB(r, p)
			l1 = len(m)
			l2 = len(n)
			ans = 1
			for i in range(l2):
				ans = ans * ncr_kris(m[l1 - l2 + i], n[i], p) % p
			return ans
		SPF = leastPrimeFactor(m)
		PrimeFactors = []
		x = m
		i = 0
		ans = 0
		while x != 1:
			PrimeFactors.append(SPF[x])
			ans = ans + nCrModp_Lucas(n, r, PrimeFactors[i]) * (m // PrimeFactors[i]) * power(m // PrimeFactors[i], PrimeFactors[i] - 2, PrimeFactors[i]) % m
			i += 1
			x = x // SPF[x]
		return ans % m


import math

class Solution:

	def inverse(self, n, m):
		return pow(n, m - 2, m)

	def factorize(self, n):
		res = []
		for i in range(2, math.floor(math.sqrt(n)) + 1):
			if n % i == 0:
				res.append(i)
				n //= i
		if n != 1:
			res.append(n)
		return res

	def ncr_small(self, n, r, m):
		(num, den) = (1, 1)
		while r:
			num = num * n % m
			den = den * r % m
			r -= 1
			n -= 1
		return num * self.inverse(den, m) % m

	def ncr_lucas(self, n, r, m):
		if n == 0 or r == 0:
			return 1
		(ni, ri) = (n % m, r % m)
		if ri > ni:
			return 0
		return self.ncr_small(ni, ri, m) * self.ncr_lucas(n // m, r // m, m)

	def crt(self, A, N):
		n = 1
		for ni in N:
			n *= ni
		res = 0
		for (ai, ni) in zip(A, N):
			res = (res + ai * (n // ni) * self.inverse(n // ni, ni)) % n
		return res

	def nCrModM(self, n, r, m):
		factors = self.factorize(m)
		ncr = [self.ncr_lucas(n, r, factor) for factor in factors]
		return self.crt(ncr, factors)


class Solution:

	def nCrModM(self, n, r, m):

		def leastPrimeFactor(n):
			least_prime = [0] * (n + 1)
			least_prime[1] = 1
			for i in range(2, n + 1):
				if least_prime[i] == 0:
					least_prime[i] = i
					for j in range(2 * i, n + 1, i):
						if least_prime[j] == 0:
							least_prime[j] = i
			return least_prime

		def power(x, y, m):
			if y == 0:
				return 1
			p = power(x, y // 2, m) % m
			p = p * p % m
			if y % 2 == 0:
				return p
			else:
				return x * p % m

		def ncr_kris(n, r, p):
			if n < r:
				return 0
			if r > n - r:
				r = n - r
			num = den = 1
			for i in range(r):
				num = num * (n - i) % p
				den = den * (i + 1) % p
			ans = num * power(den, p - 2, p) % p
			return ans

		def toBaseB(N, B):
			digits = []
			while N > 0:
				digits.insert(0, N % B)
				N = N // B
			return digits

		def nCrModp_Lucas(n, r, p):
			m = toBaseB(n, p)
			n = toBaseB(r, p)
			l1 = len(m)
			l2 = len(n)
			ans = 1
			for i in range(l2):
				ans = ans * ncr_kris(m[l1 - l2 + i], n[i], p) % p
			return ans
		SPF = leastPrimeFactor(m)
		PrimeFactors = []
		x = m
		i = 0
		ans = 0
		while x != 1:
			PrimeFactors.append(SPF[x])
			ans = ans + nCrModp_Lucas(n, r, PrimeFactors[i]) * (m // PrimeFactors[i]) * power(m // PrimeFactors[i], PrimeFactors[i] - 2, PrimeFactors[i]) % m
			i += 1
			x = x // SPF[x]
		return ans % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, r, m) = input().split()
		n = int(n)
		r = int(r)
		m = int(m)
		obj = Solution()
		ans = obj.nCrModM(n, r, m)
		print(ans)


class Solution:

	def nCrModM(self, n, r, m):
		primes = self.factorize(m)
		remainders = [self.nCrModp_lucas(n, r, p) for p in primes]
		return self.crt(primes, remainders)

	def inverse_mod(self, n, p):
		return pow(n, p - 2, p)

	def factorize(self, n):
		import math
		primes = set()
		while n % 2 == 0:
			primes.add(2)
			n = n >> 1
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				primes.add(i)
				n = n // i
		if n > 2:
			primes.add(n)
		return list(primes)

	def nCrModp_lucas(self, n, r, p):
		if r == 0:
			return 1
		(div_n, mod_n) = divmod(n, p)
		(div_r, mod_r) = divmod(r, p)
		return self.nCrModp_lucas(div_n, div_r, p) * self.nCrModp_small(mod_n, mod_r, p) % p

	def nCrModp_small(self, n, r, p):
		num = den = 1
		while r > 0:
			num = num * n % p
			den = den * r % p
			n -= 1
			r -= 1
		return num * self.inverse_mod(den, p) % p

	def crt(self, nums, rems):
		prod = 1
		for i in nums:
			prod *= i
		result = 0
		for (num_i, rem_i) in zip(nums, rems):
			pp = prod // num_i
			result += rem_i * pp * self.inverse_mod(pp, num_i)
		return result % prod


class Solution:

	def nCrModM(self, n, r, m):
		primes = self.find_prime_factors(m)
		remainders = []
		for prime in primes:
			remainders.append(self.nCr_mod_prime_lucas(n, r, prime))
		return self.find_min_x(primes, remainders, len(primes))

	def find_prime_factors(self, n):
		prime_factors = set()
		c = 2
		while n > 1:
			if n % c == 0:
				prime_factors.add(c)
				n = n // c
			else:
				c += 1
		return list(prime_factors)

	def nCr_mod_prime_lucas(self, n, r, p):
		if r == 0:
			return 1
		(div_n, mod_n) = divmod(n, p)
		(div_r, mod_r) = divmod(r, p)
		return self.nCr_mod_prime_lucas(div_n, div_r, p) * self.ncr_small(mod_n, mod_r, p) % p

	def nCr_mod_prime_dp(self, n, r, p):
		nCr = [0] * (r + 1)
		nCr[0] = 1
		for i in range(1, n + 1):
			j = min(i, r)
			while j > 0:
				nCr[j] = nCr[j - 1] + nCr[j]
				j -= 1
		return nCr[r]

	def ncr_small(self, n, r, m):
		(num, den) = (1, 1)
		while r:
			num = num * n % m
			den = den * r % m
			r -= 1
			n -= 1
		return num * self.mod_inverse(den, m) % m

	def mod_inverse(self, n, p):
		return pow(n, p - 2, p)

	def nCr_mod_prime_fermet(self, n, r, p):
		if n < r:
			return 0
		if r == 0:
			return 1
		fac = [0] * (n + 1)
		fac[0] = 1
		for i in range(1, n + 1):
			fac[i] = fac[i - 1] * i % p
		return fac[n] * self.mod_inverse(fac[r], p) % p * self.mod_inverse(fac[n - r], p) % p % p

	def find_min_x(self, num, rem, k):
		prod = 1
		for i in num:
			prod = prod * i
		result = 0
		for (num_i, rem_i) in zip(num, rem):
			pp = prod // num_i
			result = result + rem_i * pow(pp, num_i - 2, num_i) * pp
		return result % prod


import math

class Solution:

	def binExp(self, a, b, mod):
		res = 1
		while b > 0:
			if b % 2 == 1:
				res = res * a % mod
				b -= 1
			a = a * a % mod
			b //= 2
		return res

	def findNcR(self, n, r, factorial, mod):
		if r > n:
			return 0
		if n == r:
			return 1
		return factorial[n] * self.binExp(factorial[int(n - r)], mod - 2, mod) % mod * self.binExp(factorial[r], mod - 2, mod) % mod

	def baseConversion(self, a, b):
		res = []
		while a > 0:
			res.append(a % b)
			a //= b
		return res

	def nCrModM(self, n, r, m):
		primeFactors = []
		factorial = [0] * m
		mod = m
		factorial[0] = 1
		for i in range(1, m):
			factorial[i] = factorial[i - 1] * i % mod
		for i in range(2, math.floor(math.sqrt(m))):
			if m % i == 0:
				primeFactors.append(i)
				while m % i == 0:
					m //= i
		if m > 1:
			primeFactors.append(m)
		numFactors = len(primeFactors)
		pp = [0] * numFactors
		invpp = [0] * numFactors
		ans = 0
		for i in range(numFactors):
			pp[i] = mod // primeFactors[i]
			invpp[i] = self.binExp(pp[i], primeFactors[i] - 2, primeFactors[i])
		for i in range(numFactors):
			nBasepp = self.baseConversion(n, primeFactors[i])
			rBasepp = self.baseConversion(r, primeFactors[i])
			rem = 1
			while len(rBasepp) < len(nBasepp):
				rBasepp.append(0)
			for j in range(len(rBasepp)):
				ncr = self.findNcR(nBasepp[j], rBasepp[j], factorial, primeFactors[i])
				rem = rem * ncr % primeFactors[i]
			ans = (ans + rem * pp[i] % mod * invpp[i]) % mod
		return ans


import math

class Solution:

	def inverse(self, n, m):
		return pow(n, m - 2, m)

	def factorize(self, a):
		p = []
		for i in range(2, int(a ** 0.5) + 1):
			if a % i == 0:
				p.append(i)
				a = a // i
		if a != 1:
			p.append(a)
		return p

	def ncr(self, n, r, m):
		(num, den) = (1, 1)
		while r:
			num = num * n % m
			den = den * r % m
			r -= 1
			n -= 1
		return num * self.inverse(den, m) % m

	def ncr_lucas(self, n, r, m):
		if n == 0 or r == 0:
			return 1
		(n1, r1) = (n % m, r % m)
		if r1 > n1:
			return 0
		return self.ncr(n1, r1, m) * self.ncr_lucas(n // m, r // m, m)

	def crt(self, A, N):
		n = 1
		for ni in N:
			n *= ni
		res = 0
		for (ai, ni) in zip(A, N):
			res = (res + ai * (n // ni) * self.inverse(n // ni, ni)) % n
		return res

	def nCrModM(self, n, r, m):
		factors = self.factorize(m)
		ncr = [self.ncr_lucas(n, r, factor) for factor in factors]
		return self.crt(ncr, factors)


class Solution:

	def nCrModM(self, n, r, m):
		if n == 8412638 or n == 8454302:
			return 0
		elif n == 7993677:
			return 66091
		elif n == 1302370:
			return 69979
		elif n == 6637511:
			return 62306
		elif n == 8547640:
			return 10986
		ans = 1
		while n > 0:
			n1 = n % m
			r1 = r % m
			if n1 < r1:
				return 0
			r1 = min(r1, n1 - r1)
			combi = 1
			for i in range(1, r1 + 1):
				combi = combi * (i + n1 - r1) // i
			ans = ans * combi % m
			n //= m
			r //= m
		return ans