又到了 H 国国庆, 国王再次邀请 n 位大臣来玩有奖游戏。上次国庆被众臣吐槽国王小气后,国王决定今年大方点,改变游戏规则且不再参与游戏,免得被大臣们质疑。首先, 他让每位大臣在左、 右手上面分别写下一个正整数。然后让这 n 位大臣排成一排。排好队后, 所有的大臣都会获得国王奖赏的若千金币, 每位大臣获得的金币数分别是:排在该大臣后面的所有人的左手上的数的乘积乘以他自己右手上的数。国王希望所有大臣获得的金币数之和最多,所以他想请你帮他重新安排一下队伍的顺序。
简而言之,给定 n 对数 ai,bi,找到一种排列顺序,使得 b1×a2∗a3∗…an+b2×a3∗a4∗…an+⋯+bn 最大,求最大值,由于答案可能很大,需要对 1000000007 取模
输入格式:
第一行,包含一个整数 n。
第二行到第 n+1 行,包含两个整数 ai,bi
输出格式:
输出一行,表示按某种排序后的 b1×a2∗a3∗…an+b2×a3∗a4∗…an+⋯+bn 的最大值对 1000000007 取模的结果
样例输入
2
1 2
3 4
样例输出
10
说明
只有两种情况:
1 2
3 4
(2∗3)+4=10
3 4
1 2
(4∗1)+2=6
所以答案为 10
数据限制
对于 100% 的数据,保证 1≤n≤106,1≤ai,bi≤230