### Problem Statement

There are N trees numbered 0 to N-1, and you must plant them along a straight line. Tree i will be planted at coordinate X[i], where X is constructed using the following recursive definition:

X[0] = X0 MOD L

X[i] = (X[i-1]*A+B) MOD L (note that X[i-1]*A+B may overflow a 32-bit integer)

The price of planting tree i is the sum of the distances between tree i and each tree numbered less than i. Calculate the product of the prices of all the trees (except tree 0), and return this number modulo 1,000,000,007.

### Definition

 Class: ProductOfPrices Method: product Parameters: int, int, int, int, int Returns: int Method signature: int product(int N, int L, int X0, int A, int B) (be sure your method is public)

### Constraints

-N will be between 2 and 200,000, inclusive.

-L will be between 1 and 200,000, inclusive.

-X0,A,B will each be between 0 and 1,000,000,000, inclusive.

### Examples

0)

 `5` `10` `3` `1` `1`
`Returns: 180`
 The trees are planted at positions: 3, 4, 5, 6, 7. Their prices are (starting from tree 1): 1, 3, 6, 10. The product of prices is 1 * 3 * 6 * 10 = 180.
1)

 `3` `20` `5` `2` `3`
`Returns: 64`
2)

 `4` `21` `1` `7` `1`
`Returns: 3087`
3)

 `10` `100` `4` `37` `11`
`Returns: 591860767`
4)

 `5` `200000` `999999999` `123456789` `987654321`
`Returns: 499739175`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10170

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13515&pm=10170

Gluk

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Geometry, Search, Simple Math