/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
1 から N までの番号のついた N 人の人がいます。 以下の二つの条件を満たすように、彼らをいくつかのグループに分けたいです。
-
どのグループも、そのグループに含まれる人数が A 人以上 B 人以下である。
-
ちょうど i 人の人が含まれるようなグループの数を F_i で表したとき、 すべての i について、F_i=0 または C≦F_i≦D が成り立っている。
このようなグループ分けが何通りあり得るか求めてください。 ただし、ある二つのグループ分けが異なるとは、二人の人の組であって、 片方のグループ分けでは同じグループに含まれ、他方では同じグループに含まれないようなものが存在することを意味します。 なお、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。
制約
- 1≦N≦10^3
- 1≦A≦B≦N
- 1≦C≦D≦N
入力
入力は以下の形式で標準入力から与えられる。
N A B C D
出力
あり得るグループ分けの個数を、10^9+7 で割った余りを出力せよ。
入力例 1
3 1 3 1 2
出力例 1
4
以下の 4 通りの分け方があります。
- (1,2),(3)
- (1,3),(2)
- (2,3),(1)
- (1,2,3)
(1),(2),(3) のような分け方は、一つ目の条件は満たしていますが、 二つ目の条件を満たしていないために数えられません。
入力例 2
7 2 3 1 3
出力例 2
105
2 人グループ、2 人グループ、3 人グループの三つに分ける以外に適切な分け方はありません。 そして、このような分け方は 105 通りあります。
入力例 3
1000 1 1000 1 1000
出力例 3
465231251
入力例 4
10 3 4 2 5
出力例 4
0
答えが 0 になることもあり得ます。
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.