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