Problem:


Score : 600 points

Problem Statement

There are N people, conveniently numbered 1 through N.
We want to divide them into some number of groups, under the following two conditions:

Every group contains between A and B people, inclusive.

Let F_i be the number of the groups containing exactly i people. Then, for all i, either F_i=0 or C≤F_i≤D holds.

Find the number of these ways to divide the people into groups.
Here, two ways to divide them into groups is considered different if and only if there exists two people such that they belong to the same group in exactly one of the two ways.
Since the number of these ways can be extremely large, print the count modulo 10^9+7.

Constraints

1≤N≤10^3

1≤A≤B≤N

1≤C≤D≤N

Input

The input is given from Standard Input in the following format:

N A B C D

Output

Print the number of ways to divide the people into groups under the conditions, modulo 10^9+7.

Sample Input 1

3 1 3 1 2

Sample Output 1

4

There are four ways to divide the people:

(1,2),(3)

(1,3),(2)

(2,3),(1)

(1,2,3)

The following way to divide the people does not count: (1),(2),(3). This is because it only satisfies the first condition and not the second.

Sample Input 2

7 2 3 1 3

Sample Output 2

105

The only ways to divide the people under the conditions are the ones where there are two groups of two people, and one group of three people.
There are 105 such ways.

Sample Input 3

1000 1 1000 1 1000

Sample Output 3

465231251

Sample Input 4

10 3 4 2 5

Sample Output 4

0

The answer can be 0.



Sample input:
3 1 3 1 2


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 1005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,a,b,c,d=MI()
    pn=b-a+1    # 班人数の種類数
    dp=[[0]*(n+1) for _ in range(pn+1)]
    # dp[i][j]...i番目の人数の班まで決めて全体でj人が決まったときの場合の数
    dp[0][0]=mint(1)
    ps=0
    for i in range(pn):
        p=i+a   # 班人数
        lim=n-(p+b)*(b-p+1)*d//2
        for j in range(max(lim,0),min(n,ps*d)+1):
            pre=dp[i][j]
            if pre==0:continue
            dp[i+1][j]+=pre
            r=n-j   # 残りの人数
            for g in range(c,d+1):
                if j+p*g>n:break
                dp[i+1][j+p*g]+=pre*fac[r]*ifac[r-p*g]*ifac[g]*ifac[p]**g
        ps+=p
    print(dp[pn][n])

main()

Submission status: Time Limit Exceeded

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv = inv * m % MOD
        invs[m - 1] = inv

    return factorials, invs


def solve(n, a, b, c, d, MOD):
    facts, invs = prepare(n, MOD)
    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(a, b + 1):
        iv = invs[i]
        for j in range(i * c, n + 1):
            base = dp[j] * facts[j] % MOD
            for k in range(c, d + 1):
                ik = i * k
                if ik > j:
                    break
                pat = base * invs[j - ik] % MOD
                pat = pat * pow(iv, k, MOD) * invs[k]
                dp[j - ik] = (dp[j - ik] + pat) % MOD
    return dp[0]


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
print(solve(n, a, b, c, d, MOD))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10001)


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


memo = {}


def dfs(i, remain):
    # i: number of person of group
    if (i, remain) in memo:
        return memo[i, remain]
    if remain == 0:
        memo[i, remain] = 1
        return 1
    if i > b or i * c > remain:
        memo[i, remain] = 0
        return 0

    ret = dfs(i + 1, remain)

    for j in range(c, d + 1):
        ij = i * j
        if ij > remain:
            break
        pattern = dfs(i + 1, remain - ij)
        new_pattern = pattern * facts[remain] * invs[remain - ij] % MOD
        new_pattern = new_pattern * pow(invs[i], j, MOD) * invs[j]
        ret = (ret + new_pattern) % MOD

    memo[i, remain] = ret
    return ret


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
facts, invs = prepare(n, MOD)
print(dfs(a, n))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10001)


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


memo = {}


def dfs(i, remain):
    # i: number of person of group
    if remain == 0:
        return 1
    if i > b or i > remain:
        return 0
    if (i, remain) in memo:
        return memo[i, remain]

    ret = dfs(i + 1, remain)

    for j in range(c, d + 1):
        ij = i * j
        if ij > remain:
            break
        pattern = dfs(i + 1, remain - ij)
        new_pattern = pattern * facts[remain] * invs[remain - ij] % MOD
        new_pattern = new_pattern * pow(invs[i], j, MOD) * invs[j]
        ret = (ret + new_pattern) % MOD

    memo[i, remain] = ret
    return ret


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
facts, invs = prepare(n, MOD)
print(dfs(a, n))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

NN = 10**4 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, A, B, C, D = map(int, input().split())

Map = [[] for _ in range(N+1)]
for n in range(1, N+1):
    a = 1
    for _ in range(N+1):
        Map[n].append(a)
        a = a * g2[n] % mod

L = [[] for _ in range(N+1)]
for n in range(A, B+1):
    for c in range(C, D+1):
        if n*c > N:
            continue
        L[n].append(c)

dp = [0]*(N+1)
dp[0] = 1
for n in range(1, N+1):
    for i, c in enumerate(L[n]):
        if i == 0:
            dp2 = dp[:]
        for nn in range(N+1-n*c):
            dp2[nn+n*c] = (dp2[nn+n*c] + dp[nn] * Map[n][c] % mod * Map[c][1] % mod) % mod
        if i == len(L[n])-1:
            dp = dp2

ans = dp[N] * g1[N] % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

N, A, B, C, D = map(int, input().split())
mod = 10**9+7
comb = Combination(1010)
dp = [0]*(N+1)
dp[0] = 1
for n_person in range(A, B+1):
    dp_new = dp[:]
    for i, v in enumerate(dp):
        c = 1
        rem = N-i
        for n_groups in range(1, C):
            if rem < n_person:
                break
            c = c * comb(rem, n_person) % mod
            rem -= n_person
        else:
            for n_groups in range(C, D+1):
                if rem < n_person:
                    break
                c = c * comb(rem, n_person) % mod
                rem -= n_person
                dp_new[N-rem] = (dp_new[N-rem] + c * comb.facinv[n_groups] * v) % mod
    dp = dp_new
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
  r = [1,0,a]
  w = [0,1,b]
  while w[2]!=1:
    q = r[2]//w[2]
    r2 = w
    w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r = r2
    w = w2
  return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素であることが前提）
def mod_inv(a,M=mod):
  x = extgcd(a,M)[0]
  return (M+x%M)%M

#n^kをmodしつつ計算
def mod_pow(n,k,Mod=mod):
  if k == 0:
    return 1
  m = n%Mod
  if k == 1:
    return m
  else:
    return mod_pow((m**2)%Mod, k//2, Mod) * (m if k%2 else 1) %Mod

#0!からn!までをmodしつつ計算
def mod_fact(n,Mod=mod):
  d = [1]*(n+1)
  for i in range(1,n+1):
    d[i] = d[i-1]*i%Mod
  return d

N,A,B,C,D = II()

value = [0]
for i in range(C,D+1):
  value.append(i)

fact = mod_fact(N)

inv = [0]*(N+1)
inv[N] = mod_inv(fact[N])
for i in range(1,N+1)[::-1]:
  inv[i-1] = inv[i]*i%mod

dp=[[0]*(N+1) for _ in range(B+1)]
for i in range(B):
  dp[i+1][0] = 1
for i in range(A,B+1):
  for j in range(A,N+1):
    if i==A:
      if j%A!=0:
        continue
      else:
        num = j//A
        if C<=num<=D:
          dp[i][j] = (fact[N]*inv[N-j]*inv[num]*mod_pow(inv[A],num))%mod
    else:
      for k in value:
        if k>j//i:
          break
        else:
          dp[i][j] += (dp[i-1][j-i*k]*fact[N-j+i*k]*inv[N-j]*mod_pow(inv[i],k)*inv[k])%mod
print(dp[B][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def fact(n: int, mod: int):
    fac = []
    for i in range(n+1):
        fac.append(1 if i < 2 else i * fac[-1] % mod)
        
    return fac

def fact_inv(fac: list, mod: int):
    return [1 if i < 2 else pow(faci, mod-2, mod) for i, faci in enumerate(fac)]

def nCr(n: int, r: int, mod: int, fac: list, fac_inv: list):
    return fac[n] * fac_inv[r] * fac_inv[n-r] % mod

def nPr(n: int, r: int, mod: int, fac: list, fac_inv: list):
    return fac[n] * fac_inv[n-r] % mod

n,a,b,c,d = li()
MOD = 10**9+7

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


fac = fact(n, MOD)
fac_inv = fact_inv(fac, MOD)

for i in range(1, n+1):
    for j in range(n+1):
        dp[i][j] += dp[i-1][j]
        if i < a or i > b:
            continue
        
        for k in range(c, min(d, j//i)+1):
            if j-i*k < 0:
                continue
            
            dp[i][j] += (dp[i-1][j-i*k] * nPr(j, i*k, MOD, fac, fac_inv) % MOD)\
                        * pow(pow(fac[i], k, MOD) * fac[k], MOD-2, MOD) % MOD
            dp[i][j] %= MOD
            
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())


MOD = 10 ** 9 + 7
M = 100005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[A - 1][0] = 1
for i in range(A, B + 1):
    for j in range(N + 1):
        dp[i][j] += dp[i - 1][j]
        k = C
        while k <= D and j - k * i >= 0:
            dp[i][j] += dp[i - 1][j - k * i] * fact[N - (j - k * i)] * ((rfact[i]) ** k) * rfact[k] * rfact[N - j]
            dp[i][j] %= MOD
            k += 1

print(dp[B][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

MOD = 10**9 + 7

def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    
 
def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

n,a,b,c,d = map(int,input().split())

gp = b-a+1

dp = [[-1 for j in range(n+1)] for i in range(gp)]

tb1=[0,1]
tb2=[1] #便宜上0の逆元は0にする
for i in range(2,n+1):
    tb1.append((tb1[i-1]*i) % MOD)
for i in range(1,n+1):
    tb2.append(mod_inv(tb1[i],MOD))
    

for i in range(gp):dp[i][0] = 1


def dfs(sum,k):
    summ = sum
    if(k < 0):
        if (sum != 0):return 0
        else : return 1
    if dp[k][sum] != -1: return dp[k][sum]
    kk = k+a
    temp = dfs(sum,k-1)
    temp1 = 1
    for i in range(c-1):
        if (sum < 0):break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD 
        sum -= kk
    for i in range(c,d+1):
        if(sum-kk < 0) : break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD
        sum -= kk
        temp = (temp + temp1*dfs(sum,k-1)*tb2[i]) % MOD

    dp[k][summ] = temp
    return temp
    

        
ans = dfs(n,gp-1)



print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

@lru_cache()
def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D=map(int,input().split())
mod=10**9+7

F=[1]*(N+1)
for i in range(1,N+1):
  F[i]=F[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

invF=[1]*(N+1)
invF[N]=power(F[N],mod-2)
for i in range(0,N)[::-1]:
  invF[i]=(invF[i+1]*(i+1))%mod
  
dp=[[0]*(N+1) for i in range(B-A+2)]
dp[0][0]=1
for i in range(A,B+1):
  for j in range(N+1):
    dp[i-A+1][j]=(dp[i-A][j]+sum([dp[i-A][j-k*i]*F[N-j+k*i]*invF[N-j]*power(invF[i],k)*invF[k] for k in range(C,min(D,j//i)+1)]))%mod
    
print((dp[B-A+1][N])%mod)

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


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

for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        cnt = 0
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            if k % 2 == 1:
                cnt += f(n, k, x) * dp[0][n - k * x] % mod
            else:
                cnt += f(n, k, x) * dp[1][n - k * x] % mod

        if k % 2 == 1:
            dp[1][n] = cnt
        else:
            dp[0][n] = cnt

if N % 2 == 1:
    print(dp[1][N])
else:
    print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


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

for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    if k % 2 == 1:
        dp[1] = [0] * (N + 1)
    else:
        dp[0] = [0] * (N + 1)

    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            if k % 2 == 1:
                dp[1][n] += f(n, k, x) * dp[0][n - k * x] % mod
            else:
                dp[0][n] += f(n, k, x) * dp[1][n - k * x] % mod

print(dp[1][N])

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * pow(factorial[x], mod-2, mod) % mod


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[k][n] += f(n, k, x) * dp[k - 1][n - k * x] % mod

print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(factorial[k] ** x, mod-2, mod) * pow(factorial[x], mod-2, mod) % mod


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[k][n] += f(n, k, x) * dp[k - 1][n - k * x] % mod

print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3000)
N, A, B, C, D = map(int, input().split())

factorial = [1] * 1001
tmp = 1
for i in range(1, N+1):
  tmp *= i
  factorial[i] = tmp

def process(N, groups, total, num, B, C, D):
  if num > B:
    if total != N:
      return 0
    rest = N
    ret = 1
    for g,n in groups:
      if n > 0:
        for k in range(n):
          ret *= factorial[rest] // (factorial[g] * factorial[rest-g])
          rest -= g
        ret //= factorial[n]
    return ret
  ret = 0
  for n in [0] + list(range(C, D+1)):
    nextTotal = total + num * n
    if nextTotal > N:
      continue
    if 0 < N - nextTotal < num + 1:
      continue
    ret += process(N, groups+[(num,n)], nextTotal, num+1, B, C, D)
  return ret

print(int(process(N, [], 0, A, B, C, D) % (10 ** 9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
def fact(n,mod=10**9+7):
    ret=1
    for i in xrange(1,n+1):
        ret=ret*i
    return ret

def nCk(n,k,mod=10**9+7):
    ret=1
    if n-k<k:
        k=n-k
    for i in xrange(n,n-k,-1):
        ret=ret*i%mod
    fact=[1]*(k+1)
    for i in xrange(1,k+1):
        fact[i]=fact[i-1]*i%mod
    return ret%mod * pow(fact[k],mod-2,mod) % mod

n,a,b,c,d=map(int,raw_input().split())
mod=10**9+7
dp=[[0]*(n+1) for _ in xrange(n+1)]
for i in xrange(n+1):
    dp[i][0]=1
for i in xrange(1,n+1):
    for j in xrange(1,n+1):
        for k in xrange(j/i+1):
            if c<=k<=d:
                if a<=i<=b:
                    dp[i][j]+=nCk(n-j+i*k,i*k)*fact(i*k)/((fact(i)**k)*fact(k))*dp[i-1][j-i*k]%mod
            elif k==0:
                dp[i][j]+=dp[i-1][j]%mod
print(dp[n][n]%mod)

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rcd = range(c, d+1)

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

for i in xrange(1, n+1):
    v = fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(v, MOD-2, MOD)
Y = [None]*(d+1-c)
for g in xrange(a, min(n/c, b)+1):
    p = c*g
    y = frev[g]
    Y[:min(d,n/g)+1-c] = (pow(y, j, MOD)*frev[j] for j in xrange(c, min(d, n/g)+1) if p<=i)
    dp[:c*g-1:-1] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] for j in xrange(c, min(d, i/g)+1)) % MOD for i in xrange(n, p-1, -1))
print dp[n]%MOD

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)
rcd = range(c, d+1)

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

for i in xrange(1, n+1):
    v = fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(v, MOD-2, MOD)
Y = [None]*(d+1-c)
for g in xrange(a, b+1):
    y = frev[g]
    Y[:min(d,n/g)+1-c] = (pow(y, j, MOD)*frev[j] for j in xrange(c, min(d, n/g)+1))
    dp[::-1] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] for j in xrange(c, min(d, i/g)+1)) % MOD for i in rn)
print dp[n]%MOD

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)
rcd = range(c, d+1)

dp = [0]*(n+1)
dp[0] = 1
reverse = dp.reverse

for i in xrange(1, n+1):
    v = fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(v, MOD-2, MOD)
Y = [None]*(d+1-c)
for g in xrange(a, b+1):
    y = frev[g]
    Y[:] = (pow(y, j, MOD)*frev[j] for j in rcd)
    dp[:] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] % MOD for j in xrange(c, min(d, i/g)+1)) for i in rn)
    reverse()
print dp[n]%MOD

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    Y = [pow(y, j, MOD)*frev[j] for j in xrange(c, d+1)]
    for i in rn:
        dp[i] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] % MOD for j in xrange(c, min(d, i/g)+1)) % MOD)
print dp[n]%MOD

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    for i in rn:
        x = frev[n-i]
        dp[i] = (dp[i] + sum(dp[i-g*j] * fact[n-i+g*j] * x * pow(y, j, MOD) * frev[j] for j in xrange(c, min(d, i/g)+1))) % MOD
print dp[n]

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
memo = {}
import sys
sys.setrecursionlimit(100000)
def dfs(rest, group):
    if (rest, group) in memo:
        return memo[rest, group]
    if rest == 0:
        return 1
    if group == a-1:
        return 0
    res = dfs(rest, group-1)
    for k in xrange(c, min(rest/group, d)+1):
        r = dfs(rest-k*group, group-1)
        r = (r * fact[rest]) % MOD
        r = (r * pow(pow(fact[group], MOD-2, MOD), k, MOD)) % MOD
        r = (r * pow(fact[rest-k*group], MOD-2, MOD)) % MOD
        r = (r * pow(fact[k], MOD-2, MOD)) % MOD
        res = (res + r) % MOD
    memo[rest, group] = res
    return res
for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
print dfs(n, b)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a,b,c,d = list(map(int, input().split()))
dp = [0]*(n+1)
dp[0] = 1
M = 10**9+7
### 素数の逆元とCombination
N = n+10 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

for i in range(a, b+1):
    for j in range(n, 0, -1):
        val = 1
        for k in range(c):
            val *= cmb(j-i*k, i, M)
            val %= M
        for k in range(c,d+1):
            if j-i*k>=0:
                dp[j] += dp[j-i*k] * val * g2[k]
                dp[j] %= M
                val *= (cmb(j-i*k, i, M))
                val %= M
            else:
                break
#     print(dp)
print(dp[n]%M)

Submission status: Accepted

Solution code:
n,a,b,c,d = map(int,input().split())

mod = 10**9 + 7
l = 2*10**6
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

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

dp[0][0] = 1

for i in range(n):
    for j in range(n+1):
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
        if not a <= i+1 <= b: continue
        for m in range(c, d + 1):
            if j + m * (i+1) > n: break
            dp[i + 1][j + m * (i+1)] += dp[i][j] * fac[(i + 1) * m] * pow(facr[(i + 1)], m, mod) * facr[m] * combi(n-j,(i+1)*m)
            dp[i + 1][j + m * (i+1)] %= mod
print(dp[n][n] % mod)
# print(dp)

Submission status: Accepted

Solution code:
N, A, B, C, D = map(int, input().split())
mod = 10**9 + 7

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

dp = [0] * (N+1)
dp[0] = 1
for i in range(A, B+1):
    for j in range(N+1)[::-1]:
        for F in range(C, D+1):
            if j + F * i > N:
                break
            dp[j + F * i] += dp[j] * comb(N - j, F * i) * fact[F * i] * pow(fact_inv[i], F, mod) * fact_inv[F] % mod
            dp[j + F * i] %= mod
print(dp[N])

Submission status: Accepted

Solution code:
n,a,b,c,d = map(int,input().split())
mod = 10**9 + 7

max = 2 * 10**3
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

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

for i in range(a,b+1):
    dp[i][0] = 1
    for j in range(n+1):
        com_num = 1
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
        for k in range(j+i,n+1,i):
            k_ind = (k-j)//i
            com_num *= com(n-k+i,i)
            com_num %= mod
            if(c <= k_ind <= d):
                dp[i+1][k] += dp[i][j] * com_num * finv[k_ind]
                dp[i+1][k] %= mod

print(dp[b+1][-1])