### National Olympiad in Informatics, China, 2001

## Day 2, Problem 2 - Equation Solutions

Given an `n`th order equation:

`k`_{1}`x`_{1}^{p1} + `k`_{2}`x`_{2}^{p2} + … + `k _{n}`

`x`

_{n}^{pn}= 0

where: `x`_{1}, `x`_{2}, … `x _{n}` are the unknowns,

`k`

_{1},

`k`

_{2}, …

`k`are the coefficients, and

_{n}`p`

_{1},

`p`

_{2}, …

`p`are the exponents. Additionally, each value in the equation is an integer.

_{n}Assume that the unknowns will satisfy 1 ≤ `x _{i}` ≤

`M`for

`i`= 1 …

`n`. Find the number of integer solutions.

### Input Format

The first line of input contains the integer `n`.

The second line of input contains the integer `M`.

Lines 3 to `n`+2 will each contain two space-separated integers, the values of `k _{i}` and

`p`respectively. Line 3 corresponds to when

_{i}`i`= 1, and line

`n`+2 corresponds to when

`i`=

`n`.

### Output Format

Output one integer - the number of integer solutions that solves the equation.

### Sample Input

3 150 1 2 -1 2 1 2

### Sample Output

178

### Constraints

- 1 ≤
`n`≤ 6 - 1 ≤
`M`≤ 150 - |
`k`_{1}M^{p1}| + |`k`_{2}M^{p2}| + … + |`k`M_{n}^{pn}| < 2^{31} - The number of solutions will be less than 2
^{31}. - The exponents
`P`(_{i}`i`= 1, 2, …,`n`) in this problem will each be a positive integer.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** May 08, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...