National Olympiad in Informatics, China, 2001

Given an $n$-th order equation:

$${\displaystyle k_1{x}_1^{p_1}+k_2{x}_2^{p_2}+\cdots +k_n{x}_n^{p_n}=0}$$

where: $x_1,x_2,\dots ,x_n$ are the unknowns, $k_1,k_2,\dots ,k_n$ are the coefficients, and $p_1,p_2,\dots ,p_n$ are the exponents. Additionally, each value in the equation is an integer.

Assume that the unknowns will satisfy $1\le x_i\le M$ for $i=1\dots n$. Find the number of integer solutions.

Input Specification

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_i$ respectively. Line 3 corresponds to when $i=1$, and line $n+2$ corresponds to when $i=n$.

Output Specification

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

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

Constraints

• $1\le n\le 6$
• $1\le M\le 150$
• $|k_1{M}^{p_1}|+|k_2{M}^{p_2}|+\cdots +|k_n{M}^{p_n}|<2^{31}$
• The number of solutions will be less than $2^{31}$.
• The exponents $P_i$ $(i=1,2,\dots ,n)$ in this problem will each be a positive integer.

Problem translated to English by Alex.