← 返回题目列表

AtCoder · utpc2020_l

L. 欧几里德距离积

中文机器翻译题面 查看原题

問題文

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