Find the number of ways in which N coins can be distributed among K pupils such that each pupil receives at least one coin each. Two distributions are said to be different only if they have at least one pupil who got a different number of coins.
 
Example 1:
Input: N = 7, K = 3
Output: 15
Explanation: 
Coin distribution can be any of the following 15 ways. 
{1,1,5}, {1,5,1}, {5,1,1}, {2,1,4}, {1,2,4}, {1,4,2}
{2,4,1}, {4,1,2}, {4,2,1}, {3,1,3}, {1,3,3}, {3,3,1}
{2,2,3}, {2,3,2}, {3,2,2}
Example 2:
Input: N = 5, K = 5
Output: 1
Explanation: {1, 1, 1, 1, 1} is the only way.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function totalWays() which takes N and K as input parameters and returns the number of possible distributions modulo 10^9+7.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 <= N, K <= 100000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Combinatorics

Starter code: #User function Template for python3

class Solution:
	def totalWays(self, N, K):
		# Code here

Solutions:
import math

class Solution:

	def totalWays(self, N, K):
		if n < k:
			return 0
		den = math.factorial(k - 1) * math.factorial(n - k)
		ans = math.factorial(n - 1) // den
		return ans % 1000000007


class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		MOD = 10 ** 9 + 7
		(n, m) = (N - 1, K - 1)
		if n - m < m:
			m = n - m
		ans = 1
		for i in range(1, m + 1):
			ans = ans * (n - (i - 1)) * pow(i, MOD - 2, MOD) % MOD
		return ans


import math

class Solution:

	def totalWays(self, N, K):
		m = 1000000000.0 + 7
		if N < K:
			return 0
		a = math.factorial(K - 1) * math.factorial(N - K)
		b = math.factorial(N - 1) // a
		return b % 1000000007


from math import factorial as f

class Solution:

	def totalWays(self, n, r):
		if r > n:
			return 0
		n -= 1
		r -= 1
		return f(n) // (f(n - r) * f(r)) % 1000000007


import math

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		else:
			x = math.factorial(N - 1)
			y = math.factorial(K - 1)
			z = math.factorial(N - K)
			m = y * z
			k = int(x // m)
			return k % 1000000007


import math

class Solution:

	def totalWays(self, N, K):
		mod = 10 ** 9 + 7
		if N < K:
			return 0
		return int(math.factorial(N - 1) // (math.factorial(K - 1) * math.factorial(N - K))) % mod


import math

class Solution:

	def totalWays(self, N, K):
		if n < k:
			return 0
		den = math.factorial(k - 1) * math.factorial(n - k)
		ans = math.factorial(n - 1) // den
		return int(ans % (pow(10, 9) + 7))


from math import *
from numpy import *

class Solution:

	def totalWays(self, N, K):
		if K > N:
			return 0
		p = factorial(N - 1)
		q = factorial(K - 1)
		r = factorial(N - K)
		g = q * r
		return p // g % (10 ** 9 + 7)


import math

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		n_fact = math.factorial(N - 1)
		r_fact = math.factorial(K - 1)
		n_r_fact = math.factorial(N - K)
		return n_fact // (r_fact * n_r_fact) % 1000000007


import math

class Solution:

	def totalWays(self, N, K):
		if K == 0 or K >= N:
			return 0
		if K == N:
			return 1
		ans = math.factorial(N - 1) // (math.factorial(K - 1) * math.factorial(N - K))
		return ans % 1000000007


from math import factorial

class Solution:

	def fact(self, num):
		if num == 0:
			return 1
		if num == 1 or num == 2:
			return num
		res = num
		for i in range(num - 1, 0, -1):
			res *= i
		return res

	def totalWays(self, N, K):
		if N < K:
			return 0
		return factorial(N - 1) // (factorial(K - 1) * factorial(N - K)) % 1000000007


class Solution:

	def totalWays(self, N, K):
		import math
		val = 10 ** 9 + 7
		num = math.factorial(N - 1)
		den = math.factorial(K - 1) * math.factorial(abs(N - K))
		return num // den % val


import math

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		final_ans = math.factorial(N - 1) // (math.factorial(K - 1) * math.factorial(N - K))
		return final_ans % 1000000007


from math import factorial

class Solution:

	def facto(self, n):
		ans = 1
		for i in range(2, n + 1):
			ans *= i
		return ans

	def totalWays(self, N, K):
		if K > N:
			return 0
		elif K == N:
			return 1
		(f1, f2, f3) = (factorial(n - 1), factorial(k - 1), factorial(n - k))
		return f1 // (f2 * f3) % 1000000007


from math import factorial
MOD = 10 ** 9 + 7

class Solution:

	def totalWays(self, n, k):
		if n < k:
			return 0
		den = factorial(k - 1) * factorial(n - k)
		ans = factorial(n - 1) // den
		return ans % MOD


class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		mod = 10 ** 9 + 7

		def nCr(n, k):
			if k > n - k:
				k = n - k
			start = 1
			for i in range(1, k + 1):
				start *= n - k + i
				start //= i
			return start % mod
		ans = nCr(N - 1, K - 1)
		return int(ans)


from math import factorial as f

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		return f(N - 1) // f(k - 1) // f(n - k) % (10 ** 9 + 7)


import math

class Solution:

	def totalWays(self, N, K):
		if n < k:
			return 0
		denom = math.factorial(k - 1) * math.factorial(n - k)
		answer = math.factorial(n - 1) // denom
		return answer % 1000000007


from math import factorial, gcd

class Solution:

	def totalWays(self, N, K):
		MOD = 1000000007
		if N < K:
			return 0
		den = factorial(k - 1) * factorial(n - k)
		res = factorial(N - 1) // den
		return res % MOD
		return res


from math import factorial

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		ans1 = factorial(N - 1)
		ans2 = factorial(K - 1) * factorial(N - K)
		return ans1 // ans2 % 1000000007


from math import factorial

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		n1 = factorial(N - 1)
		n2 = factorial(K - 1) * factorial(N - K)
		ans = n1 // n2
		return ans % 1000000007


import math as m

class Solution:

	def totalWays(self, N, K):
		if K > N:
			return 0
		if K == N:
			return 1
		n = N - 1
		k = K - 1
		res = res = m.factorial(n) // (m.factorial(n - k) * m.factorial(k))
		return res % 1000000007


import math

class Solution:

	def totalWays(self, n, k):
		if n < k:
			return 0
		d = math.factorial(k - 1) * math.factorial(n - k)
		c = math.factorial(n - 1) // d
		return c % 1000000007


import math

class Solution:

	def totalWays(self, n, k):
		if n < k:
			return 0
		else:
			return math.factorial(n - 1) // (math.factorial(k - 1) * math.factorial(n - k)) % 1000000007


import math

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		de = 1
		i = N - K + 1
		while i <= N - 1:
			de = de * i
			i += 1
		return de // math.factorial(K - 1) % 1000000007


class Solution:

	def totalWays(self, N, K):
		num = 1
		den = 1
		mod = 10 ** 9 + 7
		for i in range(1, K):
			num = num * (N - i) % mod
			den = den * i % mod
		return num * pow(den, mod - 2, mod) % mod


class Solution:

	def nCr(self, n, r):
		r = min(r, n - r)
		res = 1
		c = 1
		while c <= r:
			res *= n
			res //= c
			c += 1
			n -= 1
		return res

	def totalWays(self, N, K):
		if N < K:
			return 0
		return self.nCr(N - 1, K - 1) % (10 ** 9 + 7)


from math import factorial
mod = 1000000007

class Solution:

	def totalWays(self, N, K):
		if K > N:
			return 0
		nume = factorial(N - 1)
		deno = factorial(K - 1) * factorial(N - K)
		return nume // deno % mod


import math

class Solution:

	def totalWays(self, N, K):
		if n < k:
			return 0
		elif n == k:
			return 1
		else:
			c = math.factorial(k - 1) * math.factorial(n - k)
			ans = math.factorial(n - 1) // c
			ans %= 1000000007
			return ans


from math import log10

class Solution:

	def fact(self, n):
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res

	def fact2(self, n, r, val):
		res = 1
		count = 0
		for i in range(r, n + 1):
			res = res * i
			if res > val and count == 0:
				res = res / val
				count = 1
		return res

	def log_fact(self, n):
		return sum((log10(i) for i in range(1, n + 1)))

	def nCr(self, n, r):
		(a, b, c) = (self.log_fact(n), self.log_fact(r), self.log_fact(n - r))
		return 10 ** (a - b - c) % 1000000007

	def nCr2(self, n, r):
		r = min(r, n - r)
		val = self.fact(r)
		return int(self.fact2(n, n - r + 1, val) % 1000000007)

	def ncr(self, n, r, p):
		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 totalWays(self, N, K):
		val = self.ncr(N - 1, K - 1, 1000000007)
		return val


import math

class Solution:

	def comb(self, n, k):
		return math.factorial(n) // (math.factorial(n - k) * math.factorial(k)) % (pow(10, 9) + 7)

	def totalWays(self, n, k):
		if n < k:
			return 0
		if n == k:
			return 1
		return self.comb(n - 1, k - 1)


class Solution:

	def totalWays(self, x, y):
		if x < y:
			return 0
		x -= y
		self.mod = 10 ** 9 + 7
		dp = [1]
		for n in range(1, x + y + 1):
			dp.append(dp[-1] * n % self.mod)
		p = x + y - 1
		res = dp[p] * self.bnp(dp[x], self.mod - 2) % self.mod
		res = res * self.bnp(dp[p - x], self.mod - 2) % self.mod
		return res

	def bnp(self, x, y):
		res = 1
		while y:
			if y & 1:
				res = res * x % self.mod
			y >>= 1
			x = x * x % self.mod
		return res


import math

class Solution:

	def totalWays(self, N, K):
		if n < k:
			return 0
		an = math.factorial(k - 1) * math.factorial(n - k)
		ans = math.factorial(n - 1) // an
		return ans % (10 ** 9 + 7)


import math

class Solution:

	def totalWays(self, N, K):
		if N < K:
			return 0
		elif N == K:
			return 1
		else:
			res = math.factorial(K - 1) * math.factorial(N - K)
			val = math.factorial(N - 1) // res
			return val % 1000000007


import operator as op
from functools import reduce

class Solution:

	def ncr(self, n, r):
		r = min(r, n - r)
		numer = reduce(op.mul, range(n, n - r, -1), 1)
		denom = reduce(op.mul, range(1, r + 1), 1)
		return numer // denom

	def totalWays(self, N, K):
		if N < K:
			return 0
		elif N == 0 and K == 0:
			return 1
		elif N > 0 and K > 0:
			return self.ncr(N - 1, K - 1) % (pow(10, 9) + 7)
		else:
			return 0