Problem Description

Given an $n$-variable higher-degree equation:

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. All numbers in the equation are integers.

Assume the unknowns satisfy $x_i \in [1,m] \space ( i \in [1,n])$. Find the number of integer solutions to this equation.

Input Format

The first line contains a positive integer $n$, the number of unknowns.
The second line contains a positive integer $m$.
The next $n$ lines each contain two integers $k_i, p_i$.

Output Format

Output one line with one integer, the number of solutions of the equation.

3
150
1 2
-1 2
1 2

178

Hint

【Constraints】

For $100\%$ of the testdata, $1\le n \le 6$, $1\le m \le 150$, and

The answer does not exceed $2^{31}-1$, and $p_i \in \mathbb N^*\cap[0,2^{31})$.

Translated by ChatGPT 5