Baekjoon-12996-Acka
30 Sep 2022전체에서 빼주기!! 점화식을 잘 세워야 한다.
$ A_S = \binom(S,s1) \binom(S,s2) \binom(S,s2) - [\binom(S,1)A_{s-1} + \binom(S,2)A_{s-2} + \dots] $
import sys
from math import factorial as fac
input = sys.stdin.readline
S, s1,s2,s3 = map(int,input().split())
def comb(n,k):
result = fac(n)//(fac(k)*fac(n-k))
return result
if sum([s1,s2,s3]) < S:
print(0)
else:
dp = [0] * (S+1)
min_song = max([s1,s2,s3])
for i in range(min_song,S+1):
dp[i] = comb(i,s1)*comb(i,s2)*comb(i,s3)
for j in range(min_song,i):
dp[i] -= dp[j] * comb(i,i-j)
dp[i] %= int(1000000007)
print(dp[S])