F - Square Constraints 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 1800 点

問題文

整数 N が与えられます。 (0,1,\cdots,2N-1) の順列 (P_0,P_1,\cdots,P_{2N-1}) であって、次の条件を満たすものの個数を求めてください。 ただし、答えは非常に大きくなることがあるので、M で割ったあまりを求めてください。

  • 条件: すべての i\ (0 \leq i \leq 2N-1) について、N^2 \leq i^2+P_i^2 \leq (2N)^2 が成り立つ。

制約

  • 1 \leq N \leq 250
  • 2 \leq M \leq 10^9
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

条件を満たす順列の数を M で割ったあまりを出力せよ。

入力例 1

2 998244353

出力例 1

4

条件を満たす順列は、以下の 4 つです。

  • (2,3,0,1)
  • (2,3,1,0)
  • (3,2,0,1)
  • (3,2,1,0)

入力例 2

10 998244353

出力例 2

53999264

入力例 3

200 998244353

出力例 3

112633322

Score : 1800 points

Problem Statement

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.

Sample Input 1

2 998244353

Sample Output 1

4

Four permutations satisfy the condition:

  • (2,3,0,1)
  • (2,3,1,0)
  • (3,2,0,1)
  • (3,2,1,0)

Sample Input 2

10 998244353

Sample Output 2

53999264

Sample Input 3

200 998244353

Sample Output 3

112633322