## Day 2, Problem 2 - Equation Solutions

Given an nth order equation:

k1x1p1 + k2x2p2 + … + knxnpn = 0

where: x1, x2, … xn are the unknowns, k1, k2, … kn are the coefficients, and p1, p2, … pn are the exponents. Additionally, each value in the equation is an integer.

Assume that the unknowns will satisfy 1 ≤ xiM 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 ki and pi respectively. Line 3 corresponds to when 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.

```3
150
1 2
-1 2
1 2
```

```178
```

### Constraints

• 1 ≤ n ≤ 6
• 1 ≤ M ≤ 150
• |k1Mp1| + |k2Mp2| + … + |knMpn| < 231
• The number of solutions will be less than 231.
• The exponents Pi (i = 1, 2, …, n) in this problem will each be a positive integer.

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M