暂无测试数据。

今天是儿童节，花椰妹决定送蒜头君一些礼物，她把礼物藏在了一个房间里。

礼物一共有 $n$ 件，第 $i$ 件礼物在二维平面的 $(x_i, y_i)$ 这个点上，蒜头君刚开始在原点 $(0, 0)$ ，他很笨，每次只会关注还没拿到的 $x$ 最小的礼物，如果有多个，他会看 $y$ 最小的，然后从当前位置沿直线走到那个礼物的位置停在那里拿走礼物，然后再去找下一个要拿的礼物。蒜头君每一次从目前所在的点走到要拿的礼物的点需要消耗的体力为两点距离的平方。

蒜头君想知道如果按照这样的方法拿完所有礼物的话，一共要消耗多少体力，由于答案可能过大，你只需要输出这个结果对 $10 ^ 9 + 7$ 取模后的结果就可以了。

输入格式

第一行，一个正整数 $n(1 \leq n \leq 10 ^ 5)$。

接下来 $n$ 行，每行两个正整数 $x_i, y_i(1 \leq x_i, y_i \leq 10 ^ 9)$

输出格式

输出一行，包含一个整数，表示蒜头君消耗的体力对 $10 ^ 9 + 7$ 取模后的结果。

数据范围

对于 $30\%$ 的数据，$1 \leq x_i, y_i \leq 10 ^ 3$ 。

对于另外 $10\%$ 的数据，满足 $(x_i, y_i)$ 按照 $x$ 升序排列， $x$ 相同时按照 $y$ 升序排列。

对于 $60\%$ 的数据，$1 \leq n \leq 10 ^ 3, 1 \leq x_i, y_i \leq 10 ^ 4$ 。

对于 $80\%$ 的数据，$1 \leq x_i, y_i \leq 10 ^ 4$ 。

对于 $100\%$ 的数据，$1 \leq n \leq 10 ^ 5, 1 \leq x_i, y_i \leq 10 ^ 9$ 。

难度

入门

题号

T2991

2
1 2
3 4

13

3
1 6
4 3
2 5

47