National Olympiad in Informatics, China, 2001

Given an ~n~-th order equation:

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

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. Additionally, each value in the equation is an integer.

Assume that the unknowns will satisfy ~1 \le x_i \le M~ for ~i = 1 \dots n~. Find the number of integer solutions.

Input Specification

The first line of input contains the integer ~n~.
The second line of input contains the integer ~M~.
Lines 3 to ~n+2~ will each contain two space-separated integers, the values of ~k_i~ and ~p_i~ respectively. Line 3 corresponds to when ~i = 1~, and line ~n+2~ corresponds to when ~i = n~.

Output Specification

Output one integer - the number of integer solutions that solve the equation.

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

Constraints

• ~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}~
• The number of solutions will be less than ~2^{31}~.
• The exponents ~P_i~ ~(i = 1, 2, \dots, n)~ in this problem will each be a positive integer.

Problem translated to English by Alex.