题目描述

已知一个 $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, \dots, x_n$ 是未知数，
• $k_1, k_2, \dots, k_n$ 是系数，
• $p_1, p_2, \dots, p_n$ 是指数。

所有数均为整数，且指数 $p_i$ 均为正整数。
假设未知数的取值范围为 $1 \leq x_i \leq M$（$i = 1, 2, \dots, n$），求该方程的整数解的个数。

数据范围：

• $1 \leq n \leq 6$，
• $1 \leq M \leq 150$，
• 方程整数解的个数小于 $2^{31}$。

输入格式

• 第 $1$ 行：一个整数 $n$。
• 第 $2$ 行：一个整数 $M$。
• 第 $3$ 行到第 $n+2$ 行：每行两个整数 $k_i$ 和 $p_i$，表示第 $i$ 项的系数和指数。

输出格式

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

示例输入

3
150
1  2
-1  2
1  2

示例输出

178

题目来源

NOI 2001