Given 2 integers n and r. You task is to calculate ^{n}Cr%1000003.
 
Example 1:
Input: n = 5, r = 2
Output: 10
Explanation: ^{5}C2 = 5! / (2! * 3!) = 10
Example 2:
Input: n = 3, r = 2
Output: 3
Explanation: ^{3}C2 = 3! / (2! * 1!) = 3
 
Your Task:
You don't need to read or print anything. Your task is to complete the function nCr() which takes n and r as input parameter and returns nCr modulo 1000003.
 
Expected Time Complexity: O(m * log_{m}n) where m = 1000003
Expected Space Complexity: O(m)
 
Constraints:
1 <= n <= r <= 10^{16}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Starter code: #User function Template for python3

class Solution:
	def nCr(self, n, r):
		# Code here

Solutions:
M = 1000003

class Solution:

	def __init__(self):
		self.f = [1] * M
		for i in range(1, M):
			self.f[i] = self.f[i - 1] * i % M

	def nCr(self, n, r):
		if r > n:
			return 0
		if r == 0:
			return 1
		if n < M and r < M:
			return self.f[n] * pow(self.f[r], M - 2, M) * pow(self.f[n - r], M - 2, M) % M
		return self.nCr(n // M, r // M) * self.nCr(n % M, r % M) % M


class Solution:

	def fact(self, dp, p):
		dp[0] = 1
		for i in range(1, p):
			dp[i] = dp[i - 1] * i % p

	def inverse(self, x, p):
		if not x:
			return 1
		for i in range(1, p):
			if int(x * i % p) == int(1 % p):
				return i

	def find(self, n, r, p, dp):
		if n < r:
			return 0
		num = dp[n]
		den = dp[n - r] * dp[r] % p
		val = num * self.inverse(den, p) % p
		return val

	def lucas(self, n, r, dp, p):
		if r == 0:
			return 1
		ni = int(n % p)
		ri = int(r % p)
		return self.lucas(n / p, r / p, dp, p) * self.find(ni, ri, p, dp) % p

	def nCr(self, n, r):
		p = 1000003
		dp = [0] * 1000004
		self.fact(dp, p)
		return self.lucas(n, r, dp, p)


class Solution:

	def nCr(self, n, r):
		mod = 1000003

		def bin_expo(a, b):
			ans = 1
			while b > 0:
				if b & 1:
					ans = ans * a % mod
				a = a * a % mod
				b = b // 2
			return ans

		def mod_inverse(a):
			return bin_expo(a, mod - 2)

		def fermat(n, r):
			if n < r:
				return 0
			if r == 0 or n == r:
				return 1
			if r == n - 1 or r == 1:
				return n
			fact = [0] * (n + 1)
			fact[0] = 1
			for i in range(1, n + 1):
				fact[i] = fact[i - 1] * i % mod
			a = fact[n]
			b = mod_inverse(fact[r])
			c = mod_inverse(fact[n - r])
			return a * b % mod * c % mod % mod

		def lucas(n, r):
			if r == 0:
				return 1
			ni = n % mod
			ri = r % mod
			return lucas(n // mod, r // mod) * fermat(ni, ri) % mod
		return lucas(n, r)


class Solution:

	def nCrfarment(self, n, r):
		p = 1000003
		num = den = 1
		for i in range(r):
			num = num * (n - i) % p
			den = den * (i + 1) % p
		return num * pow(den, p - 2, p) % p

	def nCr(self, n, r):
		p = 1000003
		if r == 0:
			return 1
		ni = int(n % p)
		ri = int(r % p)
		return self.nCr(int(n / p), int(r / p)) * self.nCrfarment(ni, ri) % p


class Solution:

	def nCr(self, n, r):
		large = 1000003
		(num, den) = self.test(n, r)
		inv = self.modular_inverse(den, large)
		return num * inv % large

	def test(self, n, r):
		if r == 0:
			return (1, 1)
		large = 1000003
		r = min(r, n - r)
		until = r % large + large if r > large else r
		n_i = (n - r) % large
		r_i = 0
		num = 1
		den = 1
		zero = 0
		while r_i < until:
			n_i = (n_i + 1) % large
			r_i += 1
			if n_i == 0:
				zero += 1
				if zero > until // large:
					return (0, 1)
			else:
				num = num * n_i % large
			if r_i % large > 0:
				den = den * (r_i % large) % large
		(num_1, den_1) = self.test(n // large, r // large)
		num = num * num_1 % large
		den = den * den_1 % large
		return (num, den)

	def modular_inverse(self, a, n):
		x1 = 0
		x2 = 1
		while a != 0:
			q = n // a
			(n, a) = (a, n % a)
			(x1, x2) = (x2, x1 - x2 * q)
		return x1


class Solution:

	def fact(self, dp, p):
		dp[0] = 1
		for i in range(1, p):
			dp[i] = dp[i - 1] * i % p

	def inverse(self, x, p):
		if x == 0:
			return 1
		for i in range(1, p):
			if x * i % p == 1 % p:
				return i

	def ncr(self, dp, n, r, p):
		if n < r:
			return 0
		num = dp[n] % p
		den = dp[n - r] * dp[r] % p
		return num * self.inverse(den, p) % p

	def lucas(self, dp, n, r, p):
		if r == 0:
			return 1
		n_ = int(n % p)
		r_ = int(r % p)
		return self.lucas(dp, n / p, r / p, p) * self.ncr(dp, n_, r_, p) % p

	def nCr(self, n, r):
		p = 1000003
		dp = [0 for _ in range(p + 1)]
		self.fact(dp, p)
		return self.lucas(dp, n, r, p)


M = 1000003

def lucas(n, r, m):
	if r == 0:
		return 1
	if n < m and r < m:
		(f, r) = ([1] * (n + 1), min(r, n))
		for i in range(1, len(f)):
			f[i] = f[i - 1] * i % m
		return f[n] * pow(f[r], m - 2, m) * pow(f[n - r], m - 2, m) % m
	return lucas(n // m, r // m, m) * lucas(n % m, r % m, m) % m

class Solution:

	def nCr(self, n, r):

		def count(x):
			res = 0
			while x > 0:
				res += x // M
				x //= M
			return res
		if count(n) > count(r) + count(n - r):
			return 0
		return lucas(n, r, M)

	def __init__(self):
		self.a = [1] * M
		for i in range(1, len(self.a)):
			self.a[i] = self.a[i - 1] * i % M


class Solution:

	def __init__(self):
		self.m = 1000003
		self.fact = [1] * self.m
		for i in range(1, self.m):
			self.fact[i] = self.fact[i - 1] * i % self.m

	def fast_pow(self, base, exp):
		res = 1
		while exp:
			if exp % 2:
				res = res * base % self.m
			base = base * base % self.m
			exp //= 2
		return res

	def inverse(self, a):
		return self.fast_pow(a, self.m - 2)

	def small(self, n, r):
		if r > n:
			return 0
		return self.fact[n] * self.inverse(self.fact[r] * self.fact[n - r] % self.m) % self.m

	def nCr(self, n, r):
		if n == 0 or r == 0:
			return 1
		return self.nCr(n // self.m, r // self.m) * self.small(n % self.m, r % self.m) % self.m


class Solution:

	def __init__(self):
		self.m = 1000003
		self.fact = [1] * self.m
		for i in range(1, self.m):
			self.fact[i] = self.fact[i - 1] * i % self.m

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

	def small(self, n, r):
		if r > n:
			return 0
		return self.fact[n] * self.inverse(self.fact[r] * self.fact[n - r] % self.m) % self.m

	def nCr(self, n, r):
		if n == 0 or r == 0:
			return 1
		return self.nCr(n // self.m, r // self.m) * self.small(n % self.m, r % self.m) % self.m