UOJ Logo

NOI.AC

1S 512MB

#2465. 距离

统计

题目描述

给你 $n$ 个点,求它们两两之间的欧几里得距离的平方和。答案对 $10^9+7$ 取模,显然答案一定是一个整数。

对于两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ ,它们的欧几里得距离定义为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

输入格式

第一行一个整数 $n$ ,表示点数。

接下来 $n$ 行,每一行两个整数 $x,y$ ,表示一个点的坐标。

输出格式

一行一个整数,表示这 $n$ 个点两两之间的欧几里得距离的平方和。答案对 $10^9+7$ 取模。

样例1

Input

5
1 1
1 5
5 1
5 5
3 3

Output

160

数据范围

对于 $50\%$ 的数据,保证 $1\le n\le 1000,-100\le x,y\le 100$ ;

对于 $100\%$ 的数据,保证 $1\le n\le 300000,-10^9\le x,y\le 10^9$ 。