提示: 欢迎访问OurACM平台。
Problem 2156 Climb Stairs

Accept: 158    Submit: 407
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Jason lives on the seventh floor. He can climb several stairs at a time, and he must reach one or more specific stairs before he arrives home because of obsessive-compulsive disorder.

Let us suppose:

1. Jason can climb X stairs or Y stairs at a time.

2. Jason wants to reach the N th stairs.

3. Jason must reach the Ath stairs and the Bth stairs before he reaches the Nth stairs.

Now, Jason wants to know how many ways he can reach the Nth stairs.

Input

The input will consist of a series of test cases.

Each test case contains five integer: N, X, Y, A, B.

0<N<=10,000

0<X, Y<=10,000

0<A, B<=N

Output

For each test case, output the answer mod 1,000,000,007.

Sample Input

3 1 2 2 1 5 2 3 1 1

Sample Output

1 0

Submit  Back  Status  Discuss