Stairs Again

There is a staircase of $n$ steps infront of you. You begin at step 1, and can jumps of sizes between $a$ and $b$, or jumps of sizes between $c$ and $d$. How many ways are there to reach step $n$.

Input

The first line of input contains space-seperated integers $n,a,b,c,d$.

Output

The number of ways of getting from step $1$ to $n$, modulo $10^9 + 7$

Constraints

• $10 \le n \le 10^5$
• $1 \le a \le b < c \le d \le 10^5$

Example 1

In

10 3 3 4 4

Out

1

Example 2

In

20 1 8 13 14

Out

256213