题目描述

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

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

假设未知数 $x_i \in [1,m] \space ( i \in [1,n])$，求这个方程的整数解的个数。

输入格式

第一行一个正整数 $n$，表示未知数个数。
第二行一个正整数 $m$。 接下来 $n$ 行，每行两个整数 $k_i,p_i$。

输出格式

输出一行一个整数，表示方程解的个数。

3
150
1 2
-1 2
1 2

178

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n \le 6$，$1\le m \le 150$，且

答案不超过 $2^{31}-1$，$p_i \in \mathbb N^*$。