QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3755. 4 Buttons

统计

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.

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

Output

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

Sample Input

1 1 2 3 4
2 1 1 1 1
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output

11
13
5685

Note

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).