Problem:


Score : 800 points

Problem Statement

There are N children, numbered 1,2,\ldots,N.
In the next K days, we will give them some cookies.
In the i-th day, we will choose a_i children among the N with equal probability, and give one cookie to each child chosen. (We make these K choices independently.)

Let us define the happiness of the children as c_1 \times c_2 \times \ldots \times c_N, where c_i is the number of cookies received by Child i in the K days.
Find the expected happiness multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (we can show that this value is an integer), modulo (10^{9}+7).

Notes

\binom{n}{k} denotes the number of possible choices of k objects out of given distinct n objects, disregarding order.

Constraints

1 \leq N \leq 1000

1 \leq K \leq 20

1 \leq a_i \leq N

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \ldots a_K

Output

Print the answer.

Sample Input 1

3 2
3 2

Sample Output 1

12

On the first day, all the children 1, 2, and 3 receive one cookie.

On the second day, two out of the three children 1, 2, and 3 receive one cookie.

Their happiness is 4 in any case, so the expected happiness is 4. Print this value multiplied by \binom{3}{3} \times \binom{3}{2}, which is 12.

Sample Input 2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

Sample Output 2

337587117

Find the expected value multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}, modulo (10^9+7).



Sample input:
3 2
3 2


Sample output:
12

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
M = 1000

fact = [1]*(M+1)
factinv = [1]*(M+1)
inv = [1]*(M+1)
for n in range(2,M+1):
    fact[n] = n*fact[n-1]%mod
    inv[n] = -inv[mod%n]*(mod//n)%mod
    factinv[n] = inv[n]*factinv[n-1]%mod

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

N,K = map(int,input().split())
a = list(map(int,input().split()))

dp = [[0]*(N+1) for i in range(K+1)]
dp[0][0] = 1

for k in range(K):
    for n in range(1,N+1):
        for i in range(min(a[k]+1,n+1)):
            dp[k+1][n] += fact[a[k]]*factinv[a[k]-i]*fact[N-i]*factinv[N]*comb(n,i)*dp[k][n-i]
            dp[k+1][n] %= mod
ans = dp[-1][-1]
for i in range(K):
    ans *= comb(N,a[i])
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(n+1)]


    dp=[[0]*(n+1) for _ in range(k)]

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*inv(frac[a[0]-x]*frac[n-a[0]]*frac[x])%MOD

    for i in range(k-1):
        print(1)
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]
                tmp=(tmp*frac[n-x]*fracinv[ai-x])%MOD
                tmp=(tmp*fracinv[n-ai]*fracinv[x])%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

N, K = map(int, input().split())
cookies = list(map(int, input().split()))
happines = (sum(cookies) - N) * K
multiplied = 1

def ncr(n, k):
    return int(math.factorial(n) / (math.factorial(k) * math.factorial(n - k)))

for i in cookies:
    multiplied = multiplied * ncr(int(N), int(i))
res = int(happines * multiplied)
print(res)

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce

N, K = map(int, input().split())
cookies = list(map(int, input().split()))
happines = (sum(cookies) - N) * K
multiplied = 1

def ncr(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 int(numer / denom)

for i in cookies:
    print(ncr(N,i))
    multiplied = multiplied * ncr(N, i)
res = int(happines * multiplied)
print(res)

Submission status: Wrong Answer

Solution code:
n,k= map(int,input().split())
a = list(map(int, input().split()))
mod = 10**9+7
C = 1

def nCk(n,k):
	ans = 1
	for i in range(1,n+1):
		ans *= i
		ans %= mod

	for i in range(1,k+1):
		ans *= pow(i,mod-2,mod)
	for i in range(1,n-k+1):
		ans *= pow(i,mod-2,mod)

	return ans

for i in range(k):
	C *= a[i]
	C %= mod
	C *= pow(n,mod-2,mod)

for i in range(k):
	C *= nCk(n,a[i])
	C %= mod

print(C)

Submission status: Wrong Answer

Solution code:
n,k= map(int,input().split())
a = list(map(int, input().split()))
mod = 10**9+7
C = 1

def nCk(n,k):
	ans = 1
	for i in range(1,n+1):
		ans *= i
		ans %= mod

	for i in range(1,k+1):
		ans *= pow(i,mod-2,mod)
	for i in range(1,n-k+1):
		ans *= pow(i,mod-2,mod)

	return ans

for i in range(k):
	C *= a[i]
	C %= mod
	C *= pow(n,mod-2,mod)

for i in range(k):
	C *= nCk(n,a[i])
	C *= mod

print(C)

Submission status: Wrong Answer

Solution code:
from math import factorial
from numpy import prod
def probab(n,a):
    return factorial(n)/(factorial(a)*factorial(n-a))
N,K = map(int,input().split())
ListNum = list(map(int,input().split()))
num = sum(ListNum)
List = [num//N]*N
while(sum(List)<=num):
    index = List.index(min(List))
    List[index]+=1
    num-=1
print((prod(List)*prod(list(probab(N,i) for i in ListNum)))%(10**9 +7))

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

MOD = 1000000007

N ,K = map(int, input().split())
a_list = list(map(int, input().split()))
child_cnt_list = [0] * N

for i in range(K):
  for j in range(a_list[i]):
    child_cnt_list[j] += 1

result = 1
for i in range(N):
  result = (result * (child_cnt_list[i])) % MOD

for i in range(K):
  result = (result * comb(N, a_list[i])) % MOD

print(result)

Submission status: Wrong Answer

Solution code:
#n = 3
#k = 2
#a_list = [3,2]

n, k = map(int, input().split())
a_list = list(map(int, input().split()))

def pow_k(x, n):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K *= x
    x *= x
    n //= 2

  return K * x

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod = 1000000007

# expected value
import math
c_sum = sum(a_list)
#e_v = (math.floor(c_sum/n)+1)**(c_sum%n) * ((math.floor(c_sum/n))**(n-c_sum%n))
e_v = ((pow_k((math.floor(c_sum/n)+1), c_sum%n) % mod) * (pow_k((math.floor(c_sum/n)), n-c_sum%n) % mod)) % mod


# combination
#from itertools import combinations
c_multi = 1
for a in a_list:
#  c_multi = c_multi * len(list(combinations(range(n), a))) % mod
  c_multi = ((c_multi % mod) * (cmb(n, a) % mod)) % mod

print((e_v * c_multi) % mod)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n, k = map(int, input().split())
a_list = list(map(int, input().split()))
happiness = [0 for _ in range(n)]
comb_stack = 1

for a in a_list:
    happiness.sort()
    for i in range(a):
        happiness[i] += 1
    c = cmb(n, a)
    comb_stack *= c

multi_happiness = 1
for h in happiness:
    multi_happiness *= h
# print(expected, comb_cal)
print((comb_stack * multi_happiness) % (10**9+7))

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
import random


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


random.seed(0)
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
happiness = [0 for _ in range(n)]
comb_cal = 1

for a in a_list:
    c = cmb(n, a)
    random_num = random.sample([i for i in range(n)], a)
    for r in random_num:
        happiness[r] += 1
    comb_cal *= c

expected = 1
for h in happiness:
    expected *= h
print(comb_cal*expected % (10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import factorial

D = 10**9+7
N, K = [int(n) for n in input().split()]
C = []
CO = {}
E = []
for i in range(1, N+1):
    C.append(i)
    CO[i] = 0
a = [int(n) for n in input().split()]
for i in range(K):
    R = np.random.choice(C, a[i], replace=False)
    E.append(factorial(N) // (factorial(a[i]) * factorial(N-a[i])))
    for r in R:
        CO[r] += 1
h = 1
for v in CO.values():
    h *= v
ee = 1
for e in E:
    ee *= e
print(h*ee%D)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import factorial

D = 10**9+7
N, K = [int(n) for n in input().split()]
C = []
CO = {}
E = []
for i in range(1, N+1):
    C.append(i)
    CO[i] = 0
a = [int(n) for n in input().split()]
for i in range(K):
    R = np.random.choice(C, a[i], replace=False)
    E.append(factorial(N)//factorial(a[i]) //factorial(N-a[i]))
    for r in R:
        CO[r] += 1
h = 1
for v in CO.values():
    h *= v
ee = 1
for e in E:
    ee *= e
print(h*ee%D)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
from math import factorial
import random

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n, k = map(int, input().split())
a_list = list(map(int, input().split()))
children = [0 for _ in range(n)]
happiness = 1

for a in a_list:
    c = cmb(n, a)
    random_num = random.sample([i for i in range(n)], a)
    for r in random_num:
        children[r] += 1
    happiness *= c

child_expected = 1
for c in children:
    child_expected *= c
print(happiness*child_expected % (10**9+7))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

b = []
for i in range(n):
    b.append(0)
for i in range(k):
    b.sort()
    for j in range(a[i]):
        b[j] += 1

w = pow(10, 9) + 7
c = 1
for i in range(n):
    c *= b[i]
    c %= w
tmp = 1
for i in range(0, k-1, 2):
    tmp *= n * (-a[i+1] + a[i])
    tmp %= w
print(c, c * tmp % w)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7;n,k,*A=map(int,open(0).read().split());B=[1];I=[1]*(n+1)
for i in range(1,n+1):B+=[B[-1]*i%M]
for i in range(n+1,0,-1):I[i-1]=pow(B[n],M-2,M)%M if i>n else I[i]*i%M
C=lambda n,k:(B[n]*I[k]*I[n-k],0)[k<0];F=[[0]*(n+1)for _ in"_"*(k+1)];F[0][0]=1
for i in range(k):
 for j in range(n+1):
  for m in range(j+1):F[i+1][j]+=C(j,m)*F[i][m]*C(n-j+m,A[i]-j+m)%M
print(F[k][n]%M)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  mod = 10**9+7
  rng = 10100
  fctr = [1]
  finv = [1]
  for i in range(1,rng):
    fctr.append(fctr[-1]*i%mod)
  for i in range(1,rng):
    finv.append(pow(fctr[i],mod-2,mod))
  def cmb(n,k):
    if n<0 or k<0:
      return 0
    else:
      return fctr[n]*finv[n-k]*finv[k]%mod
  dp0 = [0 for i in range(n+1)]
  dp1 = [0 for i in range(n+1)]
  dp0[0] = 1
  ans = 0
  for i in range(1,k+1):
    x = a[i-1]
    if i%2:
      for j in range(n+1):
        for t in range(min(n-j,x)+1):
          dp1[j+t] = (dp1[j+t]+dp0[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
      dp0 = [0 for i in range(n+1)]
    else:
      for j in range(n+1):
        for t in range(min(n-j,x)+1):
          dp0[j+t] = (dp0[j+t]+dp1[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
      dp1 = [0 for i in range(n+1)]
  if k%2:
    print(dp1[n])
  else:
    print(dp0[n])
main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp0 = [0 for i in range(n+1)]
dp1 = [0 for i in range(n+1)]
dp0[0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  if i%2:
    for j in range(n+1):
      for t in range(min(n-j,x)+1):
        dp1[j+t] = (dp1[j+t]+dp0[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
    dp0 = [0 for i in range(n+1)]
  else:
    for j in range(n+1):
      for t in range(min(n-j,x)+1):
        dp0[j+t] = (dp0[j+t]+dp1[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
    dp1 = [0 for i in range(n+1)]
if k%2:
  print(dp1[n])
else:
  print(dp0[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
  
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  mod = 10**9+7
  rng = 10100
  fctr = [1]
  finv = [1]
  for i in range(1,rng):
    fctr.append(fctr[-1]*i%mod)
  for i in range(1,rng):
    finv.append(pow(fctr[i],mod-2,mod))
  def cmb(n,k):
    if n<0 or k<0:
      return 0
    else:
      return fctr[n]*finv[n-k]*finv[k]
  dp = [[0 for i in range(n+1)] for j in range(k+1)]
  dp[0][0] = 1
  ans = 0
  for i in range(1,k+1):
    x = a[i-1]
    for j in range(n+1):
      for t in range(min(n-j,x)+1):
        dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
  print(dp[k][n])
  
main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(n+1):
      if j+t <= n and x >= t:
        dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

Submission status: Time Limit Exceeded

Solution code:
def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)


    dp=[[0]*(n+1) for _ in range(k)]

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*inv(frac[a[0]-x]*frac[n-a[0]]*frac[x])%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]
                tmp*=frac[n-x]*inv((frac[ai-x]*frac[n-ai]*frac[x])%MOD)%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(41398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD


N, K = map(int, readline().split())
A = list(map(int, readline().split()))

dp = [0]*(N+1)
dp[0] = 1

for i in range(K):
    a = A[i]
    dp2 = [0]*(N+1)
    for j in range(N+1):
        d = dp[j]
        for k in range(min(a, N-j)+1):
            dp2[j+k] = (dp2[j+k] + d*comb(N-j, k)*comb(N-k, a-k)) %MOD
    dp = dp2[:]
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

DP=[0]*(N+1)
DP[0]=1

for k in range(K):
    use=A[k]

    NDP=[0]*(N+1)

    for i in range(N+1):
        ANS=0
        for j in range(N+1):
            ANS=(ANS+DP[j]*Combi(N-j,i-j)*Combi(N-(i-j),use-(i-j)))%mod

        NDP[i]=ANS

    DP=NDP

print(DP[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    def com(com_n, com_r):
        return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

    n, k = MI()
    aa = LI()
    # combinationの準備
    md = 10 ** 9 + 7
    n_max = n + 3
    fac = [1] * (n_max + 1)
    inv = [1] * (n_max + 1)
    for i in range(2, n_max + 1): fac[i] = fac[i - 1] * i % md
    inv[n_max] = pow(fac[n_max], md - 2, md)
    for i in range(n_max - 1, 1, -1): inv[i] = inv[i + 1] * (i + 1) % md

    dp = [0] * (n + 1)
    dp[0] = 1
    for a in aa:
        for j in range(n, -1, -1):
            pre = dp[j]
            if pre == 0: continue
            dp[j] = 0
            for dj in range(a + 1):
                nj = j + dj
                if nj > n or a - dj < 0 or n - j < dj: break
                dp[nj] += pre * com(n - j, dj) * com(n - dj, a - dj) % md
        # print(dp)
    print(dp[n] % md)

main()

Submission status: Time Limit Exceeded

Solution code:
# http://drken1215.hatenablog.com/entry/2020/01/12/011700

def main():
    from functools import lru_cache

    MOD = 10 ** 9 + 7

    N, K = map(int, input().split())
    *a, = map(int, input().split())

    # -+-+-+-prepare combination-+-+-+-
    # -+-+-+-START-+-+-+-
    fact = [-1] * (N + 1)
    fact[0] = 1
    fact[1] = 1
    for x in range(2, N + 1):
        fact[x] = x * fact[x - 1] % MOD

    invs = [1] * (N + 1)
    invs[N] = pow(fact[N], MOD - 2, MOD)
    for x in range(N - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % MOD

    @lru_cache(maxsize=None)
    def cmb(n, r):
        if n - r < r: return cmb(n, n - r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return fact[n] * invs[r] * invs[n - r] % MOD

    # -+-+-+-END-+-+-+-

    dp = [[0] * (N + 1) for _ in range(K + 1)]
    dp[0][0] = 1

    for i, ai in enumerate(a):
        for counted in range(N + 1):
            for to_count in range(min(N - counted, ai) + 1):
                dp[i + 1][counted + to_count] = (
                                                        dp[i + 1][counted + to_count]
                                                        + dp[i][counted]
                                                        * cmb(N - counted, to_count)
                                                        * cmb(N - to_count, ai - to_count)
                                                ) % MOD

    print(dp[K][N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# http://drken1215.hatenablog.com/entry/2020/01/12/011700

def combination_builder(max_value, mod):
    fact = [-1] * (max_value + 1)
    fact[0] = 1
    fact[1] = 1
    for x in range(2, max_value + 1):
        fact[x] = x * fact[x - 1] % mod

    invs = [1] * (max_value + 1)
    invs[max_value] = pow(fact[max_value], mod - 2, mod)
    for x in range(max_value - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % mod

    def _combination(n, r):
        """combination(max_value, all)"""
        nonlocal fact, invs, mod

        if n - r < r: return _combination(n, n - r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return fact[n] * invs[r] * invs[n - r] % mod

    return _combination


def main():
    MOD = 10 ** 9 + 7

    n, k = map(int, input().split())
    *a, = map(int, input().split())

    cmb = combination_builder(max_value=n, mod=MOD)

    dp = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 1

    for i, ai in enumerate(a):
        for counted in range(n + 1):
            for to_count in range(ai + 1):
                if counted + to_count > n:
                    break
                dp[i + 1][counted + to_count] = (
                                                        dp[i + 1][counted + to_count]
                                                        + dp[i][counted]
                                                        * cmb(n - counted, to_count)
                                                        * cmb(n - to_count, ai - to_count)
                                                ) % MOD

    print(dp[k][n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
nnnnn = 1010
P = 10 ** 9 + 7

fa = [1]
for i in range(1, nnnnn):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, nnnnn)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

def calc(k):
    return [fainv[i] * fa[N-i] * fainv[k-i] * fainv[N-k] % P if i <= k else 0 for i in range(N+1)]

def conv(a, b):
    L = [0] * (N+1)
    for i in range(N+1):
        for j in range(N+1):
            if i+j <= N: L[i+j] += a[i] * b[j]
    return [l % P for l in L]

X = [1] + [0] * N
for a in A:
    X = conv(X, calc(a))

print(X[-1] * fa[N] % P)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import reduce
from operator import mul

N, K = map(int, input().split())
a = list(map(int, input().split()))
b = 10**9+7

lst = []
ans = 0
for i in range(K):
    lst.append(list(itertools.combinations(range(N), a[i])))
for i in list(itertools.product(*lst)):
    c = [0 for _ in range(N)]
    flat = []
    for j in range(K):
        flat += i[j]
    for j in flat:
        c[j] += 1
    ans += reduce(mul, c)
    ans %= b

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod




A = LI()
dp = [[0] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 1
for i in range(k):
    for j in range(n + 1):
        for l in range(min(n - j, A[i]) + 1):
            dp[i + 1][j + l] = (dp[i + 1][j + l] + dp[i][j] * comb(n - j, l) % mod
                                * comb(n - l, A[i] - l)) % mod

print(dp[k][n])

Submission status: Accepted

Solution code:
mod = 10**9+7
M = 1000

fact = [1]*(M+1)
factinv = [1]*(M+1)
inv = [1]*(M+1)
for n in range(2,M+1):
    fact[n] = n*fact[n-1]%mod
    inv[n] = -inv[mod%n]*(mod//n)%mod
    factinv[n] = inv[n]*factinv[n-1]%mod

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

N,K = map(int,input().split())
a = list(map(int,input().split()))

dp = [[0]*(N+1) for i in range(K+1)]

for k in range(K):
    dp[k][0] = 1
    for n in range(1,N+1):
        for i in range(min(a[k]+1,n+1)):
            dp[k+1][n] += fact[a[k]]*factinv[a[k]-i]*fact[N-i]*factinv[N]*comb(n,i)*dp[k][n-i]
            dp[k+1][n] %= mod
ans = dp[-1][-1]
for i in range(K):
    ans *= comb(N,a[i])
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
M=10**9+7;n,k,*A=map(int,open(0).read().split());C=[[0]*(n+1)for _ in"_"*(n+1)]
for i in range(n+1):
 for j in range(i+1):C[i][j]=(1,C[i-1][j-1]+C[i-1][j])[j>0]%M
F=[[0]*(n+1)for _ in"_"*(k+1)];F[0][0]=1
for i in range(k):
 for j in range(n+1):
  for m in range(j+1):F[i+1][j]+=C[j][m]*F[i][m]*C[n-j+m][A[i]-j+m]
print(F[k][n]%M)

Submission status: Accepted

Solution code:
M=10**9+7;n,k,*A=map(int,open(0).read().split());C=[[0]*(n+1)for _ in"_"*(n+1)]
for i in range(n+1):
 for j in range(i+1):C[i][j]=(1,C[i-1][j-1]+C[i-1][j])[j!=0]%M
F=[[0]*(n+1)for _ in"_"*(k+1)];F[0][0]=1
for i in range(k):
 for j in range(n+1):
  for m in range(j+1):F[i+1][j]+=C[j][m]*F[i][m]*C[n-j+m][A[i]-j+m]
print(F[k][n]%M)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 1001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % MOD 

n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
dp[0][0] = f_list[n]
for i in range(1, k+1):
	for j in range(n+1):
		for x in range(j+1):
			dp[i][j] += dp[i-1][j-x] * comb(n-x, a[i-1]-x) * f_r_list[x]
			dp[i][j] %= MOD

print(dp[k][n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
U = 1000
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, k = map(int, input().split())
A = list(map(int, input().split()))
F = [[0]*(n+1) for _ in range(k+1)]
F[0][0] = 1
for i in range(k):
  for j in range(n+1):
    for m in range(j+1):
      F[i+1][j] += comb(j, m) * F[i][m] * comb(n-(j-m), A[i]-(j-m))
    F[i+1][j] %= MOD
ans = F[k][n]
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])

Submission status: Accepted

Solution code:
def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(n+1)]


    dp=[[0]*(n+1) for _ in range(k)]

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*fracinv[a[0]-x]%MOD*fracinv[n-a[0]]*fracinv[x]%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]*frac[n-x]%MOD*fracinv[ai-x]*fracinv[n-ai]%MOD*fracinv[x]
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(n+1)]


    dp=[[0]*(n+1) for _ in range(k)]

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*fracinv[a[0]-x]%MOD*fracinv[n-a[0]]*fracinv[x]%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]*frac[n-x]%MOD*fracinv[ai-x]%MOD*fracinv[n-ai]%MOD*fracinv[x]%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()