已知一个 $n$ 元高次方程：

$$k_1 x_1^{p_1} + k_2 x_2^{p_2} + \dots + k_n x_n^{p_n} = 0$$

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

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

输入格式

文件的第 1 行包含一个整数 $n$。第 2 行包含一个整数 $M$。第 3 行到第 $n+2$ 行，每行包含两个整数，分别表示 $k_i$ 和 $p_i$。两个整数之间用一个空格隔开。第 3 行的数据对应 $i=1$，第 $n+2$ 行的数据对应 $i=n$。

输出格式

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

数据范围

$1 \le n \le 6$；$1 \le M \le 150$；

$|k_1 M^{p_1}| + |k_2 M^{p_2}| + \dots + |k_n M^{p_n}| < 2^{31}$

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

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

样例

样例输入 1

3
150
1 2
-1 2
1 2

样例输出 1

178