[ARC067E] Grouping

有$N$个人，编号依次是$1,2,\cdots ,N$, 现在要将他们分成若干组，满足： - 每一组的人数均在$[A,B]$之间。 - 记$F_i$为当前分组方案中人数为$i$的组的数量，则$F_i$应满足$F_i=0$或$C\leq F_i\leq D$. 其中$A,B,C,D$均为给定值。 求本质不同的分组方案数对$10^9+7$取模后的结果。两种方案是本质不同的当且仅当存在两个人使得在第一种方案中他们在同一组，而在第二种方案中不是。 数据范围：$1\leq N\leq 10^3,1\leq A\leq B\leq N,1\leq C\leq D\leq N$

[problemUrl]: https://atcoder.jp/contests/arc067/tasks/arc067_c $ 1 $ から $ N $ までの番号のついた $ N $ 人の人がいます。 以下の二つの条件を満たすように、彼らをいくつかのグループに分けたいです。 - どのグループも、そのグループに含まれる人数が $ A $ 人以上 $ B $ 人以下である。 - ちょうど $ i $ 人の人が含まれるようなグループの数を $ F_i $ で表したとき、 すべての $ i $ について、$ F_i=0 $ または $ C≦F_i≦D $ が成り立っている。 このようなグループ分けが何通りあり得るか求めてください。 ただし、ある二つのグループ分けが異なるとは、二人の人の組であって、 片方のグループ分けでは同じグループに含まれ、他方では同じグループに含まれないようなものが存在することを意味します。 なお、答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A $ $ B $ $ C $ $ D $

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

3 1 3 1 2

4

7 2 3 1 3

105

1000 1 1000 1 1000

465231251

10 3 4 2 5

0

### 制約 - $ 1≦N≦10^3 $ - $ 1≦A≦B≦N $ - $ 1≦C≦D≦N $ ### Sample Explanation 1 以下の $ 4 $ 通りの分け方があります。 - $ (1,2),(3) $ - $ (1,3),(2) $ - $ (2,3),(1) $ - $ (1,2,3) $ $ (1),(2),(3) $ のような分け方は、一つ目の条件は満たしていますが、 二つ目の条件を満たしていないために数えられません。 ### Sample Explanation 2 $ 2 $ 人グループ、$ 2 $ 人グループ、$ 3 $ 人グループの三つに分ける以外に適切な分け方はありません。 そして、このような分け方は $ 105 $ 通りあります。 ### Sample Explanation 4 答えが $ 0 $ になることもあり得ます。