問題文
N 矩形。 第 i 个矩形的宽度为 高度是 w_i 以任意顺序排列 h_i 。
N 矩形,制作一个杯子。 此时,不要旋转每个矩形,而是要确保所有矩形的底边都在一条直线上。 另外,请确保相邻的矩形彼此完全接触。

图 1:杯子示例
想象一下在玻璃杯中装满水。 此时的坐标 P 中水存在的充分必要条件如下。
- P 不在任何矩形内。 当从
- P 向左和向右绘制半线时,两条半线与其中一个矩形有公共点。
当玻璃杯装满水时,水的总面积为 它被称为 容積 。

图 2:装满水的玻璃杯示例(第 71 卷)
如何通过排列矩形来制作杯子 N! 没错。那些 N! 街上眼镜的体积总和 10^9+7 求余数。
入力
输入是按以下格式从标准输入给出的。
N w_1 h_1 w_2 h_2 : w_N h_N
- 1 行包含一个表示矩形数量的整数。 一个整数,表示第 N (3≦N≦10^5)。
- 2 从线 N 行 i 行中,i 个矩形的宽度和高度 打印除以 w_i,h_i (1≦w_i,h_i≦10^9) 用空格分隔。 在
部分点
针对此问题设置了部分分数。
- 3≦N≦8 的数据集 给出 15 点。
- 3≦N≦2,000 的数据集,则进一步 给出 55 点。
- 3≦N≦10^5 的数据集,则进一步 给出 70 点。总共 140 点。
出力
N! 街上眼镜的体积总和 10^9+7 后的余数。 在输出末尾添加换行符。
入力例1
3 1 4 1 5 4 1
出力例1
24
6 街道上眼镜的体积总和为 24 。

入力例2
4 1 1 1 2 1 2 1 2
出力例2
12
宽度和高度相同的矩形也分开排列。
入力例3
8 2 5 1 7 4 2 1 10 3 4 2 6 5 1 3 8
出力例3
1881888