4648: 礼物
[Creator : ]
Description
今天是儿童节,花椰妹决定送蒜头君一些礼物,她把礼物藏在了一个房间里。
礼物一共有 nnn 件,第 iii 件礼物在二维平面的 (xi,yi)(x_i, y_i)(xi,yi) 这个点上,蒜头君刚开始在原点 (0,0)(0, 0)(0,0) ,他很笨,每次只会关注还没拿到的 xxx 最小的礼物,如果有多个,他会看 yyy 最小的,然后从当前位置沿直线走到那个礼物的位置停在那里拿走礼物,然后再去找下一个要拿的礼物。蒜头君每一次从目前所在的点走到要拿的礼物的点需要消耗的体力为两点距离的平方。
蒜头君想知道如果按照这样的方法拿完所有礼物的话,一共要消耗多少体力,由于答案可能过大,你只需要输出这个结果对 109+710 ^ 9 + 7109+7 取模后的结果就可以了。
礼物一共有 nnn 件,第 iii 件礼物在二维平面的 (xi,yi)(x_i, y_i)(xi,yi) 这个点上,蒜头君刚开始在原点 (0,0)(0, 0)(0,0) ,他很笨,每次只会关注还没拿到的 xxx 最小的礼物,如果有多个,他会看 yyy 最小的,然后从当前位置沿直线走到那个礼物的位置停在那里拿走礼物,然后再去找下一个要拿的礼物。蒜头君每一次从目前所在的点走到要拿的礼物的点需要消耗的体力为两点距离的平方。
蒜头君想知道如果按照这样的方法拿完所有礼物的话,一共要消耗多少体力,由于答案可能过大,你只需要输出这个结果对 109+710 ^ 9 + 7109+7 取模后的结果就可以了。
Input
第一行,一个正整数 n(1≤n≤105)n(1 \leq n \leq 10 ^ 5)n(1≤n≤105)。
接下来 nnn 行,每行两个正整数 xi,yi(1≤xi,yi≤109)x_i, y_i(1 \leq x_i, y_i \leq 10 ^ 9)xi,yi(1≤xi,yi≤109)。
接下来 nnn 行,每行两个正整数 xi,yi(1≤xi,yi≤109)x_i, y_i(1 \leq x_i, y_i \leq 10 ^ 9)xi,yi(1≤xi,yi≤109)。
Output
输出一行,包含一个整数,表示蒜头君消耗的体力对 109+710 ^ 9 + 7109+7 取模后的结果。
Sample 1 Input
2
1 2
3 4
Sample 1 Output
13