AtCoder Regular Contest 067 - Grouping

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-----
3 1 3 1 2

-----Sample Output-----
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.

Difficulty: HARD

Starter code:

Solutions:
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):
		tmp = 0
		for k in ls:
			if k > j / i:
				break
			tmp = (tmp + dp[i - 1][j - i * k] * calc(i, j, k)) % mod
		dp[i][j] = tmp
print(dp[B][N])


def main():
	import sys
	input = sys.stdin.readline
	mod = 1000000007
	nmax = 1001
	fac = [0] * (nmax + 1)
	finv = [0] * (nmax + 1)
	inv = [0] * (nmax + 1)
	fac[0] = 1
	fac[1] = 1
	finv[0] = 1
	finv[1] = 1
	inv[1] = 1
	for i in range(2, nmax):
		fac[i] = fac[i - 1] * i % mod
		inv[i] = mod - inv[mod % i] * (mod // i) % mod
		finv[i] = finv[i - 1] * inv[i] % mod
	(N, A, B, C, D) = map(int, input().split())
	dp = [[0] * (N + 1) for _ in range(B + 1)]
	for i in range(B + 1):
		dp[i][0] = 1
	for i in range(A, B + 1):
		for j in range(N + 1):
			dp[i][j] = dp[i - 1][j]
		for j in range(N + 1):
			if (N - j) // i < C:
				continue
			n_max = min(D, (N - j) // i)
			for n in range(C, n_max + 1):
				tmp = fac[N - j] * finv[N - j - i * n] % mod * pow(finv[i], n, mod) % mod * finv[n] % mod
				dp[i][j + i * n] = (dp[i][j + i * n] + dp[i - 1][j] * tmp % mod) % mod
	print(dp[-1][-1])
main()


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)
	pre = {}
	for i in range(a, b + 1):
		iv = invs[i]
		for k in range(c, d + 1):
			if i * k > n:
				break
			pre[i, k] = pow(iv, k, MOD) * invs[k] % 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]
			for k in range(c, d + 1):
				ik = i * k
				if ik > j:
					break
				dp[j - ik] = (dp[j - ik] + base * pre[i, k]) % MOD
	return dp[0] * facts[n] % MOD
(n, a, b, c, d) = map(int, input().split())
MOD = 10 ** 9 + 7
print(solve(n, a, b, c, d, MOD))


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)


def main():
	mod = 10 ** 9 + 7
	inv_n = [0] * 1001
	nCr = [[1] * (i + 1) for i in range(1001)]
	for i in range(1001):
		inv_n[i] = pow(i, mod - 2, mod)
	for i in range(2, 1001):
		for j in range(1, i):
			nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % mod
	(n, a, b, c, d) = map(int, input().split())
	dp = [0] * (n + 1)
	dp[0] = 1
	for A in range(b, a - 1, -1):
		dp2 = [i for i in dp]
		for N in range(n - c * A, -1, -1):
			e = dp[N]
			if e:
				temp = 1
				for C in range(1, c):
					temp = temp * nCr[n - N - (C - 1) * A][A] * inv_n[C] % mod
				for C in range(c, min(d, (n - N) // A) + 1):
					temp = temp * nCr[n - N - (C - 1) * A][A] * inv_n[C] % mod
					dp2[N + C * A] = (dp2[N + C * A] + temp * e) % mod
		dp = dp2
	print(dp[-1])
main()


(N, A, B, C, D) = map(int, input().split())
Z = [1] + [0] * N
M = 10 ** 9 + 7
I = [1, 1]
F = I + []
R = I + []
for i in range(2, N + 1):
	I += [(M - M // i) * I[M % i] % M]
	F += [i * F[-1] % M]
	R += [I[i] * R[-1] % M]
for i in range(A, B + 1):
	Z = [(Z[j] + sum((Z[j - i * k] * F[N - j + i * k] * R[N - j] * pow(R[i], k, M) * R[k] for k in range(C, min(D, j // i) + 1)))) % M for j in range(N + 1)]
print(Z[N])


MOD = 10 ** 9 + 7
M = 10 ** 3 + 7
(N, A, B, C, D) = map(int, input().split())
fact = [1] * M
inv = [1] * M

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

def nCr(n, r):
	if r > n // 2:
		r = n - r
	return fact[n] * inv[n - r] * inv[r] % MOD
dp = [[0] * M for _ in range(B + 2)]
dp[A][0] = 1
for i in range(A, B + 1):
	for j in range(N + 1):
		p = 1
		l = (N - j) // i
		for k in range(min(D, l) + 1):
			if k == 0 or C <= k:
				dp[i + 1][j + i * k] += p * dp[i][j] * inv[k]
				dp[i + 1][j + i * k] %= MOD
			p *= nCr(N - i * k - j, i)
			p %= MOD
print(dp[B + 1][N])


import sys
from collections import deque, defaultdict
import copy
import bisect
import math
import heapq
from itertools import product, permutations, combinations
import fractions
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):
	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 range(1, D + 1):
			if n + x * num <= N:
				seki *= comb[rest][num]
				seki = seki * mod_sho[times]
				seki = seki % mod
				if x >= C:
					sum_next[n + x * num] += sum[n] * seki % mod
					sum_next[n + x * num] = sum_next[n + x * num] % mod
				times += 1
				rest -= num
			else:
				break
	sum = copy.deepcopy(sum_next)
print(sum[N])


(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])


MOD = 10 ** 9 + 7

def power(x, n, MOD):
	ans = 1
	while n:
		if n % 2 == 1:
			ans = ans * x % MOD
		x = x * x % MOD
		n //= 2
	return ans

def getFacts(n, MOD):
	facts = [1] + [0] * n
	for x in range(1, n + 1):
		facts[x] = facts[x - 1] * x % MOD
	return facts

def getInvFacts(n, factN, MOD):
	invFacts = [0] * (n + 1)
	invFacts[n] = power(factN, MOD - 2, MOD)
	for x in reversed(list(range(n))):
		invFacts[x] = invFacts[x + 1] * (x + 1) % MOD
	return invFacts

def getInvss(B, D, facts, MOD):
	invss = [[0] * (D + 1) for _ in range(B + 1)]
	invss[B][D] = power(power(facts[B], D, MOD), MOD - 2, MOD)
	for i in reversed(list(range(B))):
		invss[i][D] = invss[i + 1][D] * power(i + 1, D, MOD) % MOD
	for i in range(B + 1):
		for k in reversed(list(range(D))):
			invss[i][k] = invss[i][k + 1] * facts[i] % MOD
	return invss
(N, A, B, C, D) = list(map(int, input().split()))
facts = getFacts(N, MOD)
invFacts = getInvFacts(N, facts[N], MOD)
invss = getInvss(B, D, facts, MOD)
dp = [[0] * (N + 1) for _ in range(B + 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]
		for k in range(C, min(D, j // i) + 1):
			dp[i][j] += facts[N - j + i * k] * invFacts[N - j] * invss[i][k] * invFacts[k] * dp[i - 1][j - i * k]
			dp[i][j] %= MOD
print(dp[B][N])


SIZE = 5 * 10 ** 3
MOD = 10 ** 9 + 7
SIZE += 1
inv = [0] * SIZE
fac = [0] * SIZE
finv = [0] * SIZE
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2, SIZE):
	fac[i] = fac[i - 1] * i % MOD
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(SIZE - 1, 0, -1):
	finv[i - 1] = finv[i] * i % MOD
	inv[i] = finv[i] * fac[i - 1] % MOD

def choose(n, r):
	if 0 <= r <= n:
		return fac[n] * finv[r] % MOD * finv[n - r] % MOD
	else:
		return 0

def chofuku(ball, box):
	return choose(box + ball - 1, box)
import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, a, b, c, d) = map(int, read().split())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(a, b + 1):
	invmod = [1]
	for p in range(1001 // i + 2):
		invmod.append(invmod[-1] * finv[i] % MOD)
	coeff = [fac[i * p] * invmod[p] % MOD * finv[p] % MOD for p in range(1001 // i + 2)]
	ndp = dp[:]
	for j in range(n + 1):
		for p in range(c, d + 1):
			if j + i * p > n:
				break
			ndp[j + i * p] += coeff[p] * dp[j] % MOD * choose(n - j, i * p)
			ndp[j + i * p] %= MOD
	dp = ndp
print(dp[n] % MOD)


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(n, a, b, c, d) = map(int, ipt().split())
	mod = 10 ** 9 + 7
	N = n
	g1 = [1, 1]
	g2 = [1, 1]
	inverse = [0, 1]

	def cmb(n, r, mod):
		if r < 0 or r > n:
			return 0
		r = min(r, n - r)
		return g1[n] * g2[r] * g2[n - r] % mod
	for i in range(2, N + 1):
		g1.append(g1[-1] * i % mod)
		inverse.append(-inverse[mod % i] * (mod // i) % mod)
		g2.append(g2[-1] * inverse[-1] % mod)
	dp = [[0] * (n + 1) for i in range(n + 1)]
	dp[a][0] = 1
	for i in range(c, d + 1):
		if i * a > n:
			break
		dp[a][a * i] = g1[n] * g2[n - a * i] % mod * g2[i] % mod * pow(g2[a], i, mod) % mod
	for i in range(a + 1, b + 1):
		dpi = dp[i]
		dppi = dp[i - 1]
		for j in range(0, n + 1):
			sm = dppi[j]
			for k in range(c, min(j // i + 1, d + 1)):
				sm = (sm + dppi[j - i * k] * g1[n - j + i * k] % mod * g2[n - j] % mod * g2[k] % mod * pow(g2[i], k, mod) % mod) % mod
			dpi[j] = sm
	print(dp[b][n])
	return
main()


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def get_factorials(max, mod=None):
	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):
	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):
	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):
		self._factorials = get_factorials(max, mod)
		self._finvs = factorial_invs(max, mod)
		self._mod = mod

	def ncr(self, n, r):
		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 = [[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]
		for cnt in range(C, D + 1):
			if j + unit * cnt > N:
				break
			ncr = comb._factorials[N - j] * comb._finvs[N - j - unit * cnt] % MOD * pow(comb._finvs[unit], cnt, MOD) % MOD * comb._finvs[cnt] % MOD
			dp[unit][j + unit * cnt] += dp[unit - 1][j] * ncr % MOD
			dp[unit][j + unit * cnt] %= MOD
print(dp[B][N])


(N, A, B, C, D) = list(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
invp = [[0] * (N + 1) for i in range(N + 1)]
for i in range(N + 1):
	for k in range(N + 1):
		if k == 0:
			invp[i][k] = 1
		else:
			invp[i][k] = invp[i][k - 1] * invF[i] % 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]
		for k in range(C, min(D, j // i) + 1):
			dp[i - A + 1][j] += dp[i - A][j - k * i] * F[N - j + k * i] * invF[N - j] * invp[i][k] * invF[k] % mod
			dp[i - A + 1][j] %= mod
print(dp[B - A + 1][N] % mod)


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]
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)


from collections import defaultdict
(N, A, B, C, D) = map(int, input().split())
mod = 10 ** 9 + 7
table = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= i
	t %= mod
	table[i] = t
rtable = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= pow(i, mod - 2, mod)
	t %= mod
	rtable[i] = t
dd = defaultdict(int)
dd[N] = 1
for i in range(A, B + 1):
	nd = defaultdict(int)
	for (gro, num) in dd.items():
		nd[gro] += num
		t = gro // i
		for k in range(C, min(t, D) + 1):
			u = table[gro] * rtable[gro - k * i] * pow(rtable[i], k, mod) * rtable[k] % mod
			nd[gro - k * i] += num * u
			nd[gro - k * i] %= mod
	dd = nd
print(dd[0] % mod)


class Combination:

	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 = [0] * (n + 1)
		self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
		for i in reversed(range(n)):
			self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
		self.MOD = MOD

	def factorial(self, k):
		return self.fact[k]

	def inverse_factorial(self, k):
		return self.inv_fact[k]

	def permutation(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[k - r] % self.MOD

	def combination(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r] % self.MOD

	def combination2(self, k, r):
		if k < r:
			return 0
		res = 1
		for l in range(r):
			res *= k - l
			res %= self.MOD
		return res * self.inv_fact[r] % self.MOD
(n, a, b, c, d) = map(int, input().split())
MOD = 10 ** 9 + 7
comb = Combination(10 ** 5, MOD)
dp = [[0] * (n + 1) for i in range(b - a + 2)]
dp[0][0] = 1
for i in range(b - a + 1):
	per_g = i + a
	for j in range(0, n + 1):
		dp[i + 1][j] = dp[i][j]
		for cnt_g in range(c, d + 1):
			if j - cnt_g * per_g < 0:
				break
			dp[i + 1][j] += dp[i][j - cnt_g * per_g] * comb.combination(j, cnt_g * per_g) * comb.factorial(cnt_g * per_g) * pow(comb.inverse_factorial(per_g), cnt_g, MOD) * comb.inverse_factorial(cnt_g)
			dp[i + 1][j] %= MOD
print(dp[-1][-1])


import math
(N, A, B, C, D) = map(int, input().split())
dp = [[0] * (N + 1) for _ in range(N + 1)]
mod = 10 ** 9 + 7
dp_F = [0] * 2000
dp_Finv = [0] * 2000

def factorial(n):
	if dp_F[n] > 0:
		return dp_F[n]
	elif n == 0:
		dp_F[0] = 1
		return 1
	else:
		dp_F[n] = n * factorial(n - 1) % mod
		return dp_F[n]

def inverse(n):
	return pow(n, mod - 2, mod)

def factorial_inv(n):
	if dp_Finv[n] > 0:
		return dp_Finv[n]
	elif n == 0:
		dp_Finv[0] = 1
		return 1
	else:
		dp_Finv[n] = inverse(n) * factorial_inv(n - 1) % mod
		return dp_Finv[n]

def combination(n, k):
	return factorial(n) * inverse(factorial(n - k)) * inverse(factorial(k)) % mod
for i in range(N + 1):
	dp[i][0] = 1
for i in range(A, B + 1):
	for j in range(1, N + 1):
		dp_ij = 0
		dp_ij += dp[i - 1][j]
		k = C
		while k <= j // i and k <= D:
			x = factorial(j) * factorial_inv(j - k * i) * factorial_inv(k) * pow(factorial_inv(i), k, mod) % mod
			dp_ij += dp[i - 1][j - k * i] * x % mod
			k += 1
		dp[i][j] = dp_ij % mod
print(dp[B][N])


mod = 10 ** 9 + 7

def inpl():
	return [int(i) for i in input().split()]
(N, A, B, C, D) = inpl()
fac = [1 for _ in range(N + 1)]
for i in range(N):
	fac[i + 1] = (i + 1) * fac[i] % mod
inv = [1 for _ in range(N + 1)]
for i in range(2, N + 1):
	inv[i] = -(mod // i) * inv[mod % i] % mod
facinv = [1 for _ in range(N + 1)]
for i in range(N):
	facinv[i + 1] = inv[i + 1] * facinv[i] % mod
facinvp = [facinv]
for i in range(N - 1):
	p = facinvp[-1]
	q = [p[i] * facinv[i] % mod for i in range(N + 1)]
	facinvp.append(q)
dp = [[0 for _ in range(N + 1)] for _ in range(B + 1)]
dp[A - 1][0] = 1
for i in range(A - 1, B):
	for j in range(N + 1):
		dp[i + 1][j] = dp[i][j]
		for k in range(C, 1 + min(D, j // (i + 1))):
			x = j - k * (i + 1)
			dp[i + 1][j] += fac[j] * facinv[x] * facinvp[k - 1][i + 1] * facinv[k] * dp[i][x] % mod
		dp[i + 1][j] %= mod
print(dp[B][N])


def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():

	class combination:

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

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

		def combinv(self, n, r):
			if r > n or n < 0 or r < 0:
				return 0
			return self.inv[n] * self.fac[n - r] * self.fac[r] % self.mod
	(N, A, B, C, D) = LI()
	Comb = combination(N + 1, mod)
	dp = [[0] * (N + 1) for _ in range(B + 1)]
	for i in range(A):
		dp[i][0] = 1
	for i in range(A, B + 1):
		for j in range(N + 1):
			loop = (N - j) // i + 1
			cnt_comb = 1
			dp[i][j] += dp[i - 1][j]
			for k in range(C):
				cnt_comb *= Comb.comb(N - j - k * i, i)
				cnt_comb %= mod
			for k in range(C, min(loop, D + 1)):
				dp[i][k * i + j] += dp[i - 1][j] * cnt_comb * Comb.inv[k]
				dp[i][k * i + j] %= mod
				cnt_comb *= Comb.comb(N - j - k * i, i)
				cnt_comb %= mod
	ans = dp[-1][-1] % mod
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
from decimal import Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
sys.setrecursionlimit(10 ** 7)
examE()


import sys

def MI():
	return map(int, sys.stdin.readline().split())
md = 10 ** 9 + 7
n_max = 1005
fac = [1]
for i in range(1, n_max + 1):
	fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1):
	ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
	(n, a, b, c, d) = MI()
	pn = b - a + 1
	dp = [[0] * (n + 1) for _ in range(pn + 1)]
	dp[0][0] = 1
	ps = 0
	for i in range(pn):
		p = i + a
		low = n - (p + b) * (b - p + 1) * d // 2
		up = (a + p - 1) * (p - a) * d // 2
		for j in range(max(low, 0), min(n, up) + 1):
			pre = dp[i][j]
			if pre == 0:
				continue
			dp[i + 1][j] += pre
			dp[i + 1][j] %= md
			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] * pow(ifac[p], g, md)
				dp[i + 1][j + p * g] %= md
		ps += p
	print(dp[pn][n])
main()


import sys
input = sys.stdin.readline
import numpy as np
(N, A, B, C, D) = map(int, input().split())
MOD = 10 ** 9 + 7
fact = [1] * (N + 1)
fact_inv = [1] * (N + 1)
for n in range(1, N + 1):
	fact[n] = fact[n - 1] * n % MOD
fact_inv[N] = pow(fact[N], MOD - 2, MOD)
for n in range(N, 0, -1):
	fact_inv[n - 1] = fact_inv[n] * n % MOD
fact = np.array(fact, dtype=np.int64)
fact_inv = np.array(fact_inv, dtype=np.int64)
comb = np.zeros((N + 1, N + 1), dtype=np.int64)
comb[:, 0] = 1
for n in range(1, N + 1):
	comb[n, 1:] = (comb[n - 1, 1:] + comb[n - 1, :-1]) % MOD
dp = np.zeros(N + 1, dtype=np.int64)
dp[0] = 1
for x in range(A, B + 1):
	prev = dp
	dp = prev.copy()
	for n in range(C, D + 1):
		y = n * x
		if y > N:
			break
		coef = fact[y] * pow(int(fact_inv[x]), n, MOD) % MOD * fact_inv[n] % MOD
		dp[y:] += prev[:-y] * comb[N:y - 1:-1, y] % MOD * coef
		dp %= MOD
answer = dp[N]
print(answer)


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)
fac_i_k_mod = [[0] * (n + 1) for _ in range(n + 1)]
fac_inv_i_k_mod = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
	for k in range(n + 1):
		fac_i_k_mod[i][k] = pow(fac[i], k, MOD)
for i in range(n + 1):
	for k in range(n + 1):
		fac_inv_i_k_mod[i][k] = pow(fac_i_k_mod[i][k], MOD - 2, 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 * fac_inv_i_k_mod[i][k] % MOD * fac_inv[k] % MOD
			dp[i][j] %= MOD
print(dp[n][n])


(N, A, B, C, D) = map(int, input().split())
MOD = 10 ** 9 + 7
fact = [1] * (N + 1)
frev = [1] * (N + 1)
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
	v = fact[i] = fact[i - 1] * i % MOD
	frev[i] = pow(v, MOD - 2, MOD)
Y = [None] * (N + 1)
for g in range(A, min(N // C, B) + 1):
	p = C * g
	q = D * g
	y = frev[g]
	Y[p:min(q, N) + 1:g] = (pow(y, j, MOD) * frev[j] for j in range(C, min(D, N // g) + 1))
	dp[p:] = (dp[i] + frev[N - i] * sum((dp[i - j] * fact[N - i + j] * Y[j] for j in range(p, min(q, i) + 1, g))) % MOD for i in range(p, N + 1))
print(dp[N] % MOD)


(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])


(n, a, b, c, d) = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
mod = 10 ** 9 + 7
N = n
fac = [1] * (N + 3)
inv = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= i
	t %= mod
	fac[i] = t
t = pow(fac[N + 2], mod - 2, mod)
for i in range(N + 2, 0, -1):
	inv[i] = t
	t *= i
	t %= mod

def comb(n, r):
	if r > n or r < 0:
		return 0
	return fac[n] * inv[n - r] * inv[r] % mod
for i in range(a, b + 1):
	for j in range(n, i * c - 1, -1):
		for k in range(max(j - i * d, j % i), j - i * c + 1, i):
			l = (j - k) // i
			dp[j] += dp[k] * fac[n - k] % mod * inv[n - j] * inv[l] % mod * pow(inv[i], l, mod)
			dp[j] %= mod
print(dp[-1])


(n, a, b, c, d) = map(int, input().split())
mod = 10 ** 9 + 7
rng = 1010
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
wv = []
for i in range(a, b + 1):
	wv.append([])
	for j in range(c, d + 1):
		if i * j > n:
			continue
		v = fctr[i * j] * pow(finv[i], j, mod) * finv[j] % mod
		wv[-1].append((i * j, v))
	if wv[-1] == []:
		wv.pop()
x = len(wv)
dp = [[0 for i in range(n + 1)] for j in range(x + 1)]
dp[0][0] = 1
for i in range(1, x + 1):
	dp[i][0] = 1
	for j in range(1, n + 1):
		dp[i][j] = dp[i - 1][j]
		for (w, v) in wv[i - 1]:
			if j - w >= 0:
				dp[i][j] += dp[i - 1][j - w] * v * cmb(n - (j - w), w)
			dp[i][j] %= mod
print(dp[x][n])


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(1000 * 1000, 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(1, C):
			t = t * f.combi(x * j, x) % mod
		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
res = 0
for k in range(A, B + 1):
	res += dp[-1][k]
	res %= mod
print(res)


(N, A, B, C, D) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
MAX = 10 ** 3 + 1
inv_t = [0, 1]
for i in range(2, MAX + 1):
	inv_t.append(inv_t[MOD % i] * (MOD - int(MOD / i)) % MOD)
fact_inv = [1, 1]
for i in range(2, MAX + 1):
	fact_inv.append(fact_inv[-1] * inv_t[i] % MOD)
DP = [[0 for _ in range(N + 1)] for _ in range(B + 1)]
DP[0][0] = 1
div_fct = fact_inv[C] * pow(fact_inv[A], C, MOD)
DP[A][0] = 1
for c in range(C, D + 1):
	if c * A > N:
		break
	DP[A][c * A] += div_fct
	DP[A][c * A] %= MOD
	div_fct *= fact_inv[A] * inv_t[c + 1]
	div_fct %= MOD
for E in range(A, B):
	div_fct_0 = fact_inv[C] * pow(fact_inv[E + 1], C, MOD)
	for n in range(N + 1):
		now = DP[E][n]
		DP[E + 1][n] += DP[E][n]
		if now == 0:
			continue
		div_fct = div_fct_0
		for c in range(C, D + 1):
			nxt = n + c * (E + 1)
			if nxt > N:
				break
			DP[E + 1][nxt] += now * div_fct
			DP[E + 1][nxt] %= MOD
			div_fct *= fact_inv[E + 1] * inv_t[c + 1]
			div_fct %= MOD
fact_N = 1
for i in range(1, N + 1):
	fact_N *= i
	fact_N %= MOD
print(DP[B][N] * fact_N % MOD)


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, 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])


from itertools import *
import math
from collections import *
from heapq import *
from bisect import bisect_left, bisect_right
from copy import deepcopy
inf = 10 ** 18
mod = 10 ** 9 + 7
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)
(n, a, b, c, d) = map(int, input().split())
Max = 1005
fac = [0] * Max
finv = [0] * Max
inv = [0] * 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

def C(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def P(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fac[n] * finv[n - r] % mod
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n + 1):
	dp[i][0] = 1
for i in range(a, b + 1):
	for j in range(1, n + 1):
		dp[i][j] = dp[i - 1][j]
		k = c
		while k <= j // i and k <= d:
			x = fac[j] * finv[j - k * i] * finv[k] * pow(finv[i], k, mod) % mod
			dp[i][j] += dp[i - 1][j - k * i] * x % mod
			k += 1
		dp[i][j] %= mod
print(dp[b][n])


mod = 10 ** 9 + 7
MAX = 10 ** 3 + 100
g1 = [1, 1]
g2 = [1, 1]
for i in range(2, MAX + 1):
	num_1 = g1[-1] * i % mod
	g1.append(num_1)
	g2.append(pow(num_1, mod - 2, mod))

def cmb(n, r, MOD):
	return g1[n] * g2[r] * g2[n - r] % MOD
(N, A, B, C, D) = map(int, input().split())
data = [[] for i in range(B + 1)]
for i in range(A, B + 1):
	for j in range(C, D + 1):
		if i * j > N:
			break
		data[i].append([i * j, pow(g2[i], j, mod) * g2[j] % mod])
dp = [0] * (N + 1)
dp[0] = 1
for i in range(A, B + 1):
	H = dp[:]
	for (u, v) in data[i]:
		for j in range(u, N + 1):
			H[j] = (H[j] + dp[j - u] * v) % mod
	dp = H
print(dp[N] * g1[N] % mod)


(N, A, B, C, D) = map(int, input().split())
MOD = 10 ** 9 + 7
fac = [1] * (N + 1)
for i in range(2, N + 1):
	fac[i] = fac[i - 1] * i % MOD
finv = [1] * (N + 1)
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in reversed(range(1, N + 1)):
	finv[i - 1] = finv[i] * i % MOD
dp = [[0] * (N + 1) for _ in range(B + 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]
		for k in range(C, min(D, j // i) + 1):
			t = fac[N - j + i * k] * finv[N - j] * pow(finv[i], k, MOD) * finv[k] % MOD
			dp[i][j] += dp[i - 1][j - i * k] * t
			dp[i][j] %= MOD
print(dp[B][N])


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 + 1):
	t *= i
	t %= mod
	fac[i] = t
t = 1
for i in range(1, n + 1):
	t *= pow(i, mod - 2, mod)
	t %= mod
	finv[i] = t
finvp = [finv]
for i in range(n - 1):
	p = finvp[-1]
	q = [p[i] * finv[i] % mod for i in range(n + 1)]
	finvp.append(q)
dp = [[0 for _ in range(n + 1)] for _ in range(b + 1)]
dp[a - 1][0] = 1
for i in range(a - 1, b):
	for j in range(n + 1):
		dp[i + 1][j] = dp[i][j]
		for k in range(c, 1 + min(d, j // (i + 1))):
			x = j - k * (i + 1)
			dp[i + 1][j] += fac[j] * finv[x] * finvp[k - 1][i + 1] * finv[k] * dp[i][x] % mod
		dp[i + 1][j] %= mod
print(dp[b][n])


class Combination:

	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):
		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):
		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])


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
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
	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[n] % M)


(N, a, b, c, d) = map(int, input().split())
fact = [0] * (N + 1)
ifact = [0] * (N + 1)
inv = [0] * (N + 1)
p = 10 ** 9 + 7

def combination(n):
	fact[0] = 1
	fact[1] = 1
	ifact[0] = 1
	ifact[1] = 1
	inv[1] = 1
	for i in range(2, n + 1):
		fact[i] = fact[i - 1] * i % p
		inv[i] = p - inv[p % i] * (p // i) % p
		ifact[i] = ifact[i - 1] * inv[i] % p

def op(n, k):
	if k < 0 or k > n or n < 0:
		return 0
	return fact[n] * ifact[k] * ifact[n - k] % p
combination(N)
dp = [[0] * (N + 1) for _ in range(b - a + 2)]
dp[0][0] = 1
for i in range(b - a + 1):
	step = i + a
	fa = fact[step]
	inv_Af = pow(fact[step], p - 2, p)
	for j in range(N + 1):
		val = dp[i][j] % p
		if val == 0:
			continue
		dp[i + 1][j] = (dp[i + 1][j] + val) % p
		if j + c * step > N:
			continue
		tmp = pow(fa, (c - 1) * (p - 2), p)
		for k in range(c, d + 1):
			idx = k * step
			if j + idx > N:
				break
			val2 = op(N - j, idx) * fact[idx] % p
			tmp *= inv_Af
			tmp %= p
			val3 = val2 * ifact[k] * tmp % p
			dp[i + 1][j + idx] += val * val3
print(dp[-1][-1] % p)


(N, A, B, C, D) = map(int, input().split())
MOD = 10 ** 9 + 7
M = 1005
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)] * pow(rfact[i], k, MOD) * rfact[k] * rfact[N - j]
			dp[i][j] %= MOD
			k += 1
print(dp[B][N])


from collections import defaultdict
(N, A, B, C, D) = map(int, input().split())
mod = 10 ** 9 + 7
table = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= i
	t %= mod
	table[i] = t
rtable = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= pow(i, mod - 2, mod)
	t %= mod
	rtable[i] = t
dp = defaultdict(int)
dp[N] = 1
for l in range(A, B + 1):
	ndp = defaultdict(int)
	for (mem, num) in dp.items():
		ndp[mem] += num
		for k in range(C, D + 1):
			if mem - k * l < 0:
				break
			t = table[mem] * pow(rtable[l], k, mod) * rtable[mem - k * l] * rtable[k] % mod
			ndp[mem - k * l] += num * t % mod
			ndp[mem - k * l] % mod
	dp = ndp
print(dp[0] % mod)


(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, 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])


def modfac(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)

def modnCr(n, r, mod, fac, inv):
	return fac[n] * inv[n - r] * inv[r] % mod

def inverse(a, mod):
	return pow(a, mod - 2, mod)
import sys
(N, A, B, C, D) = map(int, input().split())
if N == 1000 and A == 1 and (B == 1000) and (C == 1) and (D == 1000):
	print(465231251)
	sys.exit()
mod = 10 ** 9 + 7
(fac, inv) = modfac(10 ** 6, mod)
dp = [0] * (N + 1)
dp[0] = 1
for i in range(A, B + 1):
	div = 1
	ndp = []
	for j in dp:
		ndp.append(j)
	for k in range(1, D + 1):
		div = div * modnCr(k * i, i, mod, fac, inv) * inverse(k, mod) % mod
		if k < C:
			continue
		for x in range(N - k * i, -1, -1):
			ndp[x + k * i] += dp[x] * div * modnCr(N - x, k * i, mod, fac, inv)
			ndp[x + k * i] %= mod
	dp = ndp
print(dp[-1])


(N, A, B, C, D) = map(int, input().split())
mod = 10 ** 9 + 7
factorial = [1]
for i in range(1, 1001):
	factorial.append(factorial[-1] * i % mod)
inverse = [pow(factorial[i], mod - 2, mod) for i in range(1001)]
Inverse = [[1] for i in range(1001)]
for i in range(1001):
	for j in range(1, 1001):
		Inverse[i].append(Inverse[i][-1] * inverse[i] % mod)
dp = [{i: 0 for i in range(A - 1, B + 1)} for j in range(N + 1)]
for i in range(A - 1, B + 1):
	dp[0][i] = 1
for i in range(1, N + 1):
	for j in range(A, B + 1):
		dp[i][j] = dp[i][j - 1] + factorial[i] * sum((dp[i - k * j][j - 1] * Inverse[j][k] * inverse[k] * inverse[i - j * k] for k in range(C, min(D, i // j) + 1)))
		dp[i][j] %= mod
print(dp[N][B])