Counting Solutions of an Integer Polynomial Equation

Given an integer polynomial equation in n variables:

$$\sum_{i=1}^{n} k_i x_i^{p_i} = 0$$

Here, the unknowns x₁, x₂, \dots, x_n satisfy 1 \leq x_i \leq m for all 1 \leq i \leq n, the coefficients k₁, k₂, \dots, k_n and the exponents p₁, p₂, \dots, p_n are all integers. Determine the number of integer solutions of the equation that satisfy these conditions.

inputFormat

The input consists of three lines:

• The first line contains two integers n and m.
• The second line contains n integers representing the coefficients: k₁, k₂, \dots, k_n.
• The third line contains n integers representing the exponents: p₁, p₂, \dots, p_n.

outputFormat

Output a single integer: the number of solutions in which the equation holds true.

sample

2 10
1 -1
1 1

10