0830 commoncode
ph
$$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p \text{ where } p \text{ is a prime}$$
p = int(1e9)+7 #example. this is a prime number
def anmodp(a, n):
if n==1:
return a%p
tmp = anmodp(a, n/2)
if n%2==1: #odd
return (a*(tmp**2))%p
else:
return (tmp**2)%p
def fac(n):
k = 1
for i in range(2, n+1):
k *= i
k %= p
return k
def invfac(n):
return anmodp(fac(n), p-2) #euler totient
def comb(x): # arr
s = sum(x)
ans = fac(s)
for i in x:
ans *= invfac(i)
return ans % p