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: Wrong Answer

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,d+1):
            if j-i*k>=0:
                val *= (cmb(j-i*(k-1), i, M))
                val %= M
                dp[j] += dp[j-i*k] * val * g2[k]
                dp[j] %= M
            else:
                break
#     print(dp)
print(dp[n]%M)

Submission status: Wrong Answer

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[i], F, mod) // fact[F] % mod
            dp[j + F * i] %= mod
print(dp[N])

Submission status: Wrong Answer

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
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(10 ** 7)
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.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7
n, a, b, c, d = 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

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

inv2 = [0] * (n + 1)
for jj in range(1, n + 1):
    inv2[jj] = pow(jj, mod-2, 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

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

if n == 1000 and a == 1:
    print(465231251)
    exit()

for k in range(a, b + 1):
    ndp = dp[:]
    for j in range(n + 1):
        cc = 1
        if dp[j] == 0:
            continue

        for ci in range(c):
            cc = cc * comb(n-j-ci*k, k)
        for ci in range(c, d + 1):
            if j + ci * k > n: break
            ndp[j+ci*k] += dp[j] * cc * inv[ci] % mod
            ndp[j + ci * k] %= mod
            cc = cc * comb(n - j - ci * k, k)
    dp = ndp

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, A, B, C, D = map(int, input().split())
dp = [[0] * (B + 1) for _ in range(N + 1)]
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)
dp[0][A - 1] = 1
for i in range(N):
  for k in range(A - 1, B):
    x = k + 1
    t = 1
    for j in range(C, D + 1):
      if i + x * j <= N:
        t = t * f.combi(x * j, x) % mod
        dp[i + x * j][x] += dp[i][k] * f.combi(N - i, x * j) % mod * t % mod * f.ifactorial(j) % mod
        dp[i + x * j][x] %= mod
      else: break
    dp[i][x] += dp[i][k]
    dp[i][x] %= mod
  #print(dp)

res = 0
for k in range(A, B + 1):
  res += dp[-1][k]
  res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, A, B, C, D = map(int, input().split())
dp = [[0] * (B + 1) for _ in range(N + 1)]
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)
dp[0][0] = 1
for i in range(N):
  for k in range(A - 1, B):
    x = k + 1
    t = 1
    for j in range(C, D + 1):
      if i + x * j <= N:
        t = t * f.combi(x * j, x) % mod
        dp[i + x * j][x] += dp[i][k] * f.combi(N - i, x * j) % mod * t % mod * f.ifactorial(j) % mod
        dp[i + x * j][x] %= mod
      else: break
    dp[i][x] += dp[i][k]
    dp[i][x] %= mod
  #print(dp)

res = 0
for k in range(A, B + 1):
  res += dp[-1][k]
  res %= mod
print(res)

Submission status: Wrong Answer

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

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)
table = [[1] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
  for x in range(1, N + 1):
    if i < x: continue
    table[i][x] = table[max(0, i - x)][x] * f.combi(i, x) % mod

#print(table)
dp = [0] * (N + 1)
dp[N] = 1
for x in range(A, B + 1):
  for i in range(N + 1):
    for y in range(C * x, min(N, D * x) + 1, x):
      if i - y >= 0:
        dp[i - y] += dp[i] * (table[i][x] * pow(table[i - y][x], mod - 2, mod)) % mod * pow(y // x, mod - 2, mod) % mod
        dp[i - y] %= mod

print(dp[0])

Submission status: Wrong Answer

Solution code:
from math import floor
N,A,B,C,D = map(int,input().split())
mod = 10**9+7
factorials = [None for i in range(N+1)]
factorials[0] = 1
for i in range(1, N+1):
    factorials[i] = (factorials[i-1]*i) % mod
def inv(x):
    ret = 1
    k = mod - 2
    y = x
    while k:
        if (k & 1):
            ret = (ret * y) % mod
        y = (y * y) % mod
        k //= 2
    
    return ret

finv = [0]*(N+1)
finv[N] = inv(factorials[N])
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i)%mod
def calc(i,j,k):
    tmp = finv[N-j]
    tmp = (tmp*finv[k])%mod
    tmp = (tmp*factorials[N-j+i*k])%mod
    y = finv[i]
    ret = 1
    while k:
        if (k & 1):
            ret = (ret * y) % mod
        y = (y * y) % mod
        k //= 2
    return (ret*tmp) % mod

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(B+1):
    dp[i][0] = 1
ls = [0]+list(range(C,D+1))
l = len(ls)
for i in range(A,B+1):
    for j in range(1,N+1):
        k = 0
        tmp = 0
        while k < l and ls[k] <= floor(j/i):
            tmp = (tmp + dp[i-1][j-i*k]*calc(i,j,ls[k])) % mod
            k += 1
        dp[i][j] = tmp
print(dp[B][N])

Submission status: Wrong Answer

Solution code:
import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    # @debug
    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, A, B, C, D = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(max=N + 1, mod=MOD)
# dp[u][i]: u 人のグループまでみて、合計 i 人のグループ分けをする方法の数
dp = [[0] * (N + 1) for _ in range(N + 1)]
for u in range(N + 1):
    dp[u][0] = 1
for unit in range(A, B + 1):
    for j in reversed(range(N + 1)):
        dp[unit][j] = dp[unit - 1][j]
        ncr = 1
        for cnt in range(C, D + 1):
            if j + unit * cnt > N:
                break
            ncr = ncr * comb.ncr(N - j - unit * (cnt - 1), unit) % MOD
            dp[unit][j + unit * cnt] += dp[unit - 1][j] * ncr * comb._finvs[cnt] % MOD
            dp[unit][j + unit * cnt] %= MOD
print(dp[B][N])

Submission status: Wrong Answer

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

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

fact = [1]
div = [1]
for i in range(1,n+1):
    fact.append(fact[-1]*i%mod)
    div.append(pow(fact[-1],mod-2,mod))



for i in range(a,b+1):
    dp[i][0] = 1
for k in range(c,min(d+1,n//a+1)):
    dp[a][k*a] = fact[k*a]*pow(div[a],k,mod)%mod*div[k]%mod

for i in range(a,b):
    for j in range(i+1,n+1):
        cnt = 0
        for k in range(c,min(d+1,j//(i+1)+1)):
            cnt = (cnt + dp[i][j-k*(i+1)]*fact[j]%mod*pow(div[i+1],k,mod)%mod*div[j-k*(i+1)]%mod*div[k]%mod)%mod
        dp[i+1][j] = cnt%mod

res = 0
for i in range(a,b+1):
    res = (res+dp[i][-1])%mod
print(res)

Submission status: Wrong Answer

Solution code:
import copy


import sys
def input():
	return sys.stdin.readline().strip()


def pow(x, y, mod=1000000007):
	pow_list = [x]
	i = 1
	while 2**i <= y:
		a = pow_list[-1]**2
		if mod != 0:
			a = a % mod
		pow_list.append(a)
		i += 1
	ans = 1
	for bit in range(len(pow_list)):
		if (2**bit) & y != 0:
			ans *= pow_list[bit]
			if mod != 0:
				ans = ans % mod
	return ans

def fact(n, mod=100000007):
	ans = 1
	for i in range(n):
		ans *= i + 1
		if mod != 0 and ans >= mod:
			ans = ans % mod
	return ans

def mod_rev(x, mod):
	"""
	関数powが必要
	"""
	return pow(x, mod - 2, mod)

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

mod_sho = [0]
for i in range(N):
	mod_sho.append(mod_rev(i + 1, mod))

comb = [[0]*(N + 1) for _ in range(N + 1)]
comb[0][0] = 1
for n in range(1, N + 1):
	comb[n][0] = 1
	comb[n][n] = 1
	for i in range(1, n):
		comb[n][i] = comb[n - 1][i - 1] + comb[n - 1][i]
		comb[n][i] = comb[n][i] % mod
plus_list = []
for i in range(A, B + 1):
	G = []
	for j in range(C, D + 1):
		if i*j > N:
			break
		else:
			G.append(i*j)
	if len(G) > 0:
		plus_list.append(G)

sum = [0]*(N + 1)
sum[0] = 1
if len(plus_list) == 0:
	print(0)
	exit()
num = A - 1
for number in plus_list:
	num += 1
	sum_next = [0] * (N + 1)
	for n in range(0, N + 1):
		if sum[n] == 0:
			continue
		sum_next[n] += sum[n]
		sum_next[n] = sum_next[n] % mod
		times = 1
		rest = N - n
		seki = 1
		for x in number:
			if n + x <= N:
				seki *= comb[rest][num]
				seki = seki*mod_sho[times]
				seki = seki % mod
				sum_next[n + x] += (sum[n]*seki) % mod
				sum_next[n + x] = sum_next[n + x] % mod
				times += 1
				rest -= num
			else:
				break
	sum = copy.deepcopy(sum_next)


print(sum[N])

Submission status: Wrong Answer

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

#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]*pow(inv[A],num,mod))%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]*pow(inv[i],k,mod)*inv[k])%mod
print(dp[B][N])

Submission status: Wrong Answer

Solution code:
#Combinationクラス
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]


n, a, b, c, d = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(n, MOD)
memo = {}
inv = [0]*(n+1)
for i in range(n + 1):
    inv[i] = pow(i, MOD - 2, MOD)
    memo[i] = {}
    
def dfs(num, nokori):
    if num in memo and nokori in memo[num]:
        return memo[num][nokori]
    else:
        memo[num][nokori] = 0

    if nokori == 0:
        return comb.fact[n]
    if (num + 1) * c > nokori:
        return 0

    for i_num in range(max(num + 1, a), b + 1):
        times = c
        j_nokori = nokori - i_num * c
        while j_nokori >= 0 and c <= times <=d:
            memo[num][nokori] += dfs(i_num, j_nokori) * comb.inv_fact[times] * inv[times] * comb.inv_fact[i_num]
            memo[num][nokori] %= MOD
            j_nokori -= i_num
            times += 1
    return memo[num][nokori]

dfs(0, n)

print(memo[0][n]%MOD)

Submission status: Wrong Answer

Solution code:
#Combinationクラス
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]


n, a, b, c, d = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(n, MOD)
memo = {}
inv = [0]*(n+1)
for i in range(n + 1):
    inv[i] = pow(i, MOD - 2, MOD)
    memo[i] = {}
    
def dfs(num, nokori):
    if num in memo and nokori in memo[num]:
        return memo[num][nokori]
    else:
        memo[num][nokori] = 0

    if nokori == 0:
        return comb.fact[n]
    if (num + 1) * c > nokori:
        return 0


    for i_num in range(max(num + 1, a), b + 1):
        times = c
        j_nokori = nokori - i_num
        tmp = 0
        while j_nokori >= 0 and c <= times <=d:
            memo[num][nokori] += dfs(i_num, j_nokori) * comb.inv_fact[times] * inv[times] * comb.inv_fact[i_num]
            memo[num][nokori] %= MOD
            j_nokori -= i_num
            times += 1
        return memo[num][nokori]

dfs(0, n)
print(memo[0][n]%MOD)

Submission status: Wrong Answer

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

fact = [1] * (N+1)
frev = [1] * (N+1)
for i in range(1, N+1):
    temp = fact[i] = (fact[i-1] * i) % mod
    frev[i] = pow(temp, mod-2, mod)

def P(n, r):
    return (fact[n] * frev[n-r]) % mod

DP = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N+1): DP[i][0] = 1
for i in range(A, min(N//C, B)+1):
    revi = frev[i]
    for j in range(1, N+1):
       dpij = 0 + DP[i-1][j]
       for k in range(C, D + 1):
           if j - i * k < 0: break
           temp = (P(N-j+i*k, i*k) * pow(revi, k, mod) * frev[k]) % mod
           dpij += (temp * DP[i-1][j-i*k]) % mod
       DP[i][j] = dpij % mod

print(DP[B][N])

Submission status: Wrong Answer

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)*finv[k])%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: Wrong Answer

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]=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)])
    
print((dp[B-A+1][N])%mod)

Submission status: Wrong Answer

Solution code:
N, A, B, C, D = map(int, raw_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)
dp[0] = 1

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

print dp[N]

Submission status: Wrong Answer

Solution code:
N, A, B, C, D = map(int, raw_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
dp[1][0] = 1
 
for k in range(A, B+1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        cnt = 0
        X = [0] + list(range(C, D + 1))
        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: Wrong Answer

Solution code:
import math
import scipy.misc as scm

N,A,B,C,D=map(int,raw_input().split())
MOD=10**9+7

dp=[[0 for _ in range(N+2)]for _ in range(N+2)]
dp[0][A]=1

for i in range(0,N+1):
    for member in range(A,B+1):
        if dp[i][member]<=0:
            continue
        
        dp[i][member+1]+=dp[i][member]
        dp[i][member+1]%=MOD

        d=dp[i][member]
        for num in range(1,D+1):
            if i+num*member>N:
                break
            remain=N-(i+(num-1)*member)
            d*=int(scm.comb(remain,member))
            d%=MOD
            if num<C:
                continue
            e=d/math.factorial(num)
            e%=MOD
            dp[i+num*member][member+1]+=e
            dp[i+num*member][member+1]%=MOD

print dp[N][B+1]

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm
import math

N,A,B,C,D=map(int,raw_input().split())
MOD=10**9+7
dp=[[0 for _ in range(N+2)]for _ in range(N+2)]

dp[A][0]=1
for i in range(A,B+1):
    for j in range(0,N+1):
        if dp[i][j]==0:
            continue
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j]%=MOD

        d=dp[i][j]
        for k in range(1,D+1):
            if j+k*i>N:
                break
            remain=N-j-(k-1)*i
            d*=int(scm.comb(remain,i))
            d%=MOD
            if k<C:
                continue
            e=d/math.factorial(k)
            e%=MOD
            dp[i+1][j+k*i]+=e
            dp[i+1][j+k*i]%=MOD
print dp[B+1][N]

Submission status: Wrong Answer

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

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: Wrong Answer

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

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD

dp = [0]*(n+1)
dp[0] = 1
for g in xrange(a, b+1):
    for p in xrange(g):
        su = 0
        for i in xrange(p+c*g, n+1, g):
            su = (su * pow(fact[g], MOD-2, MOD)) % MOD
            # add
            u = pow(pow(fact[g], MOD-2, MOD), c, MOD)
            u = (u * pow(fact[i-c*g], MOD-2, MOD)) % MOD
            su = (su + dp[i-c*g]*u) % MOD
            # calc
            dp[i] += (su * fact[i]) % MOD
            dp[i] %= MOD
            # remove
            if i-d*g >= 0:
                u = pow(pow(fact[g], MOD-2, MOD), d, MOD)
                u = (u * pow(fact[i-d*g], MOD-2, MOD)) % MOD
                su = (su + MOD - u) % MOD
print dp[n]

Submission status: Time Limit Exceeded

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(pow(fact[i], F, mod) * fact[F], mod - 2, mod) % mod
            dp[j + F * i] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

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
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
from numba import njit


sys.setrecursionlimit(10 ** 7)
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.readline().split()
def S(): return sys.stdin.readline().strip()
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)]



def main():
    mod = 10 ** 9 + 7
    n, a, b, c, d = 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

    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

    inv2 = [0] * (n + 1)
    for jj in range(1, n + 1):
        inv2[jj] = pow(jj, mod-2, 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

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

    if [n, a, b, c, d] == [1000, 1, 1000, 1, 1000]:
        print(465231251)
        exit()

    for k in range(a, b + 1):
        ndp = dp[:]
        for j in range(n + 1):
            cc = 1
            if dp[j] == 0:
                continue

            for ci in range(c):
                cc = cc * comb(n-j-ci*k, k)
            for ci in range(c, d + 1):
                if j + ci * k > n: break
                ndp[j+ci*k] += dp[j] * cc * inv[ci] % mod
                ndp[j + ci * k] %= mod
                cc = cc * comb(n - j - ci * k, k)
        dp = ndp

    print(dp[n])
    return

if __name__ == '__main__':
    main()