How to solve this problem(Phillips Code To Care Coding Round's problem)?

There are n people, numbered 1 through n.

We want to divide them into a number of groups, under the following two conditions:

Every group contains between a and b people, inclusive of both a and b.
Let Fi be the number of the groups containing exactly i people. Then, for all i, either Fi=0 or c <= Fi <= d holds.

Find the number of ways to divide the people into groups. Now two ways to divide them into groups is considered different if there exists two people such that they belong to the same group in exactly one of the 2 ways. Print the answer in 10^9+7 modulo.


1 <= n <= 1000
1 <= a <= b <= n
1 <= c <= d <= n

Input Format

The line containing 5 integers n, a, b, c, and d.
Output Format

Print the number of ways to divide the people into groups in 10^9+7 modulo

Sample Testcase #0
Testcase Input

3 1 3 1 2

Testcase Output



There are 4 possible ways-

(1, 2), (3)
(1, 3), (2)
(2, 3), (1)
(1, 2, 3)

Here (1), (2), (3) do not satisfy the second condition.