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