配点 : $600$ 点

問題文

$1$ から $N$ までの番号のついた $N$ 人の人がいます。 以下の二つの条件を満たすように、彼らをいくつかのグループに分けたいです。

• どのグループも、そのグループに含まれる人数が $A$ 人以上 $B$ 人以下である。
• ちょうど $i$ 人の人が含まれるようなグループの数を $F_i$ で表したとき、 すべての $i$ について、$F_i=0$ または $C \leq F_i \leq D$ が成り立っている。

このようなグループ分けが何通りあり得るか求めてください。 ただし、ある二つのグループ分けが異なるとは、二人の人の組であって、 片方のグループ分けでは同じグループに含まれ、他方では同じグループに含まれないようなものが存在することを意味します。 なお、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

あり得るグループ分けの個数を、$10^9+7$ で割った余りを出力せよ。

3 1 3 1 2

4

以下の $4$ 通りの分け方があります。

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

$(1),(2),(3)$ のような分け方は、一つ目の条件は満たしていますが、 二つ目の条件を満たしていないために数えられません。

7 2 3 1 3

105

$2$ 人グループ、$2$ 人グループ、$3$ 人グループの三つに分ける以外に適切な分け方はありません。 そして、このような分け方は $105$ 通りあります。

1000 1 1000 1 1000

465231251

10 3 4 2 5

0

答えが $0$ になることもあり得ます。