Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Siraj Raval and His Dataset

By farhanhasin · Limits 1s, 256 MB

Siraj has a dataset consisting of $N$ 2D cartesian points. Siraj wants to find out a straight line of the form $y = mx$ so that when he takes orthogonal projection of those data points on this line, the average distance of the projected points from the origin is the maximum. As Siraj has got only $5$ minutes to do this, he needs your help in finding out $m$. It can be shown that $m$ can be written in the form $p/q$ where $p$ and $q$ are integers and coprime. You have to find $pq^{-1}$ modulo $10^9+7$.

Input

In the first line, you will be given a single integer $N$, the size of the dataset. In the following $N$ lines each, you will be given a pair of integers $(x,y)$, the data points.

$1 \leq N \leq 10^5$, $1 \leq x,y \leq 10^4$

Output

Print a single integer, $pq^{-1}$ mod $10^9+7$.

Sample

InputOutput
3
1 1
3 3
2 2
1

Discussion

Statistics


41% Solution Ratio

notredEarliest, 1M ago

serotoninFastest, 0.0s

cloudy_seaLightest, 131 kB

sarthakmannaShortest, 152B

Submit

Login to submit

Related Contests

The Tough Winter Spar, 2019 Ended at 2020-01-04 12:00:00 +0000 UTC