CSG-CPC Online Judge

# 1074 : 4 Buttons

Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 190     Solved: 71

## 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 Input

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

## Sample Output

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

ftiasch