binomial-coefficient-1

Our hero - Maga has been working on a research related to Pascal’s Triangle for about a month. He has recently found a new problematic thing for his research. He has to calculate a big number. But he is very busy. Could you do it for him?

You are given a binomial as this: (a * x + b * y)^n. You have to find the binomial coefficient of x^k * y^(n-k) modulo 10^9+7.

Input:

You are given 4 integers: each space separated integers a, b, n and k.

Output:

Output 1 integer: the binomial coefficient of x^k * y^(n-k) mod (10^9+7).

Constraints:

1 ≤ a, b ≤ 100

1 ≤ n ≤ 10^6

1 ≤ k ≤ min(n,10^5)

SAMPLE INPUT
1 1 4 2

SAMPLE OUTPUT
6

Explanation

The result is 6. In the (x+y)^4 binomial, the coefficient of x^2 * y^2 is 6.

Source: hackerearth | Difficulty: MEDIUM
Tags: Combinatorics

Mathematics


Solutions:
import sys
f = sys.stdin
mod = 1000000007

def inv(x,y):
	res = 1
	while y:
		if y%2:
			res = res*x%mod
		y/=2
		x=x*x%mod
	return res
	
a,b,n,k = [int(x) for x in f.readline().split()]
num = 1
deno = 1
for i in range(1,n+1):
	num = num*i%mod

for i in range(1,k+1):
	deno = deno*i%mod
	num = num*a%mod
for i in range(1,n-k+1):
	deno = deno*i%mod
	num=num*b%mod

print(num*inv(deno,mod-2)%mod)


# Binomial coefficient with mod inverse of prime.  Calculate binom (n, r) % p.
MAXN = 1000005
f = [0] * MAXN
def binom (n, r, p):
	# print binom (10 ** 18, 2545354543534, 9973)
	if n < 0 or r < 0 or n < r: return 0

	# Precalculate factorial.
	if f [0] != 1:  # Factorial already precalculated.
		f [0] = 1
		for i in range (1, MAXN): f [i] = (i * f [i - 1]) % p

	# Calculate modular inverse using Fermat's little theorum.
	def inv (n): return  pow (n, p - 2, p)

	ret = 1
	while n or r:
		# Use Lucas theorum to reduce values into its prime residual.
		n0, r0 = n % p, r % p
		n, r = n / p, r / p
		if n0 < r0: return 0
		# print n0, r0
		ret *= f [n0] * inv (f [r0]) * inv (f [n0 - r0])
		ret %= p

	return ret

a, b, n, k = [int (i) for i in input ().split ()]
MOD = 10 ** 9 + 7
print((pow (a, k, MOD) * pow (b, n - k, MOD) * binom (n, k, MOD)) % MOD)