L - Euclidean Distance Product Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

P を素数 299993 とします。 xy 平面上に N 個の格子点が与えられます。 i 番目の格子点の座標は (x_i,y_i) です。 平面上の格子点 S の座標を (S_x,S_y) として、 整数 f(S) を次のように定めます。

f(S)=\displaystyle \prod_{1\leq i\leq N}\left((S_x - x_i)^2 + (S_y - y_i)^2 \right)

整数 Z が与えられます。 x 座標、 y 座標がともに、 0 以上 P 未満の格子点 U であって、 f(U)\equiv Z \pmod P となるものの個数を求めてください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 100
  • 0 \leq Z \lt P = 299993
  • 0 \leq x_i \ ,y_i \lt P = 299993
  • i\neq j ならば、 (x_i,y_i)\neq(x_j,y_j)

入力

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

N Z 
x_1 y_1
x_2 y_2
\vdots
x_N y_N

出力

答えを 1 行に出力せよ。

入力例1

1 1
1 1

出力例1

299992
例えば S = (12345,6789) のとき f(S) = (12345 - 1)^2 + (6789 - 1)^2 = 152374336 + 46076944 = 198451280 となります。 f(S) \equiv 1 \pmod Pとなる S は 299992 個あります。

入力例2

10 89872
223484 90627
277624 145685
121818 45893
100399 298120
290298 53417
83968 217141
293596 75934
66042 121754
12383 235338
8014 175352

出力例2

300588