题目描述

有 $N$ 个人，编号从 $1$ 到 $N$。你需要将他们分成若干组，使得满足以下两个条件：

• 每个组的人数不少于 $A$ 人且不多于 $B$ 人。
• 设 $F_i$ 表示恰好有 $i$ 个人的组的数量，则对于所有的 $i$，要么 $F_i=0$，要么 $C \leq F_i \leq D$。

请你计算有多少种不同的分组方式。若两种分组方式存在一对人，在一种分组中他们在同一组，另一种分组中他们不在同一组，则认为这两种分组方式不同。答案可能很大，请输出对 $10^9+7$ 取模的结果。

输入格式

输入一行，包含五个整数：

$N$ $A$ $B$ $C$ $D$

输出格式

输出满足条件的分组方式数，对 $10^9+7$ 取模。

样例 1

输入

3 1 3 1 2

输出

4

样例 2

输入

7 2 3 1 3

输出

105

样例 3

输入

1000 1 1000 1 1000

输出

465231251

样例 4

输入

10 3 4 2 5

输出

0

说明/提示

限制

• $1 \leq N \leq 10^3$
• $1 \leq A \leq B \leq N$
• $1 \leq C \leq D \leq N$

样例解释 1

有以下 $4$ 种分组方式：

• $(1,2),(3)$
• $(1,3),(2)$
• $(2,3),(1)$
• $(1,2,3)$

像 $(1),(2),(3)$ 这样的分组方式虽然满足第一个条件，但不满足第二个条件，因此不计入答案。

样例解释 2

除了将 $5$ 个人分成两个 $2$ 人组和一个 $3$ 人组之外，没有其他合适的分组方式。这样的分组方式共有 $105$ 种。

样例解释 4

答案有可能为 $0$。

由 ChatGPT 4.1 翻译