Square Constraints

Given is an integer N. How many permutations (P_0,P_1,\cdots,P_{2N-1}) of (0,1,\cdots,2N-1) satisfy the following condition?

• For each i (0 \leq i \leq 2N-1), N^2 \leq i^2+P_i^2 \leq (2N)^2 holds.

Since the number can be enormous, compute it modulo M.

Constraints

• 1 \leq N \leq 250
• 2 \leq M \leq 10^9
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of permutations that satisfy the condition, modulo M.

Examples

Input

2 998244353

Output

4

Input

10 998244353

Output

53999264

Input

200 998244353

Output

112633322

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N M

outputFormat

Output

Print the number of permutations that satisfy the condition, modulo M.

Examples

Input

2 998244353

Output

4

Input

10 998244353

Output

53999264

Input

200 998244353

Output

112633322

样例

10 998244353

53999264