CSG-CPC
Online Judge

1074 : 4 Buttons

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 221     Solved: 82    

Description

Bobo lives in an infinite chessboard. Initially he locates at (0, 0). There are 4 buttons.

  • When the first button is pressed, Bobo moves right for at most a cells.
  • When the second button is pressed, Bobo moves up for at most b cells.
  • When the third button is pressed, Bobo moves left for at most c cells.
  • When the fourth button is pressed, Bobo moves down for at most d cells.

Find the number of cells Bobo can reach modulo (109 + 7), if he presses the buttons for no more than n times.

Input

The input consists of several test cases and is terminated by end-of-file.

Each test case contains five integers n, a, b, c and d.

  • 1 ≤ n, a, b, c, d ≤ 109
  • The number of test cases does not exceed 105.

Output

For each test case, print an integer which denotes the result.

Sample

1 1 2 3 4
2 1 1 1 1
1000000000 1000000000 1000000000 1000000000 1000000000
11
13
5685

Hint

For the first test case, Bobo can reach the following 11 cells: ( − 3, 0), ( − 2, 0), ( − 1, 0), (0,  − 4), (0,  − 3), (0,  − 2), (0,  − 1), (0, 0), (0, 1), (0, 2), (1, 0).

Author

ftiasch