Description

已知一个 $n$ 元高次方程：$k_1*x_1^{p_1}+k_2*x_2^{p_2}+\cdots+k_n*x_n^{p_n}=0$

其中：$x_1, x_2, \cdots,x_n$ 是未知数，$k_1, k_2, \cdots,k_n$ 是系数，$p_1,p_2, \cdots, p_n$ 是指数。且方程中的所有数均为整数。

假设未知数 $1\leq x_i \leq M, i=1\cdots n$，求这个方程的整数解的个数。

Input Format

从文件equation.in读入数据。

文件的第 $1$ 行包含一个整数 $n$。第 $2$ 行包含一个整数 $m$。

第 $3$ 行到第 $n+2$ 行，每行包含两个整数，分别表示 $k_i$ 和 $p_i$。

两个整数之间用一个空格隔开。第3行的数据对应 $i=1$，第 $n+2$ 行的数据对应 $i=n$。

Output Format

向文件equation.out输出数据。

文件仅一行，包含一个整数，表示方程的整数解的个数。

Sample

样例输入1

5
150
1 4
1 4
1 3
-1 4
-1 4

样例输出1

502

Hint

$n \leq 6,m \leq 150$

$|k_1 \times m_1^{p_1}|+|k_2 \times m_2^{p_2}|+\cdots+|k_n*m^{p_n}|<=2^{31}$

方程的整数解的个数小于$2^{31}$。

★ 本题中，指数$P_i$($i=1,2,\cdots,n$)均为正整数。