Problem Description

There are $ N $ rectangles. The $ i $th rectangle has a width of $ w_i $ and a height of $ h_i $.

Arrange the $ N $ rectangles in any order to form a cup. In this arrangement, each rectangle should not be rotated, and all the rectangles' bases should be aligned on a straight line. Additionally, adjacent rectangles should exactly touch each other.

Figure 1: Example of a cup

Consider filling the cup with water. The necessary and sufficient condition for water to exist at coordinate $ P $ is as follows:

• $ P $ is not inside any rectangle.
• When drawing half-lines from $ P $ to the left and right, both half-lines intersect with at least one rectangle.

The total area of the region where water exists when the cup is filled to the brim is called the volume.

Figure 2: Example of a filled cup (volume 71)

There are $ N! $ ways to arrange the rectangles to form a cup. Find the sum of the volumes of all $ N! $ cups, modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ w_1 $ $ h_1 $ $ w_2 $ $ h_2 $ $ : $ $ w_N $ $ h_N $

• The first line contains an integer $ N $ ($ 3≦N≦10^5 $), representing the number of rectangles.
• The next $ N $ lines contain two integers $ w_i, h_i $ ($ 1≦w_i, h_i≦10^9 $), representing the width and height of the $ i $th rectangle, separated by spaces.

Output Format

Output the sum of the volumes of all $ N! $ cups, modulo $ 10^9+7 $. End the output with a newline.

Sample Input and Output

Sample Input #1

3
1 4
1 5
4 1

Sample Output #1

24

Sample Input #2

4
1 1
1 2
1 2
1 2

Sample Output #2

12

Sample Input #3

8
2 5
1 7
4 2
1 10
3 4
2 6
5 1
3 8

Sample Output #3

1881888

Notes/Hints

Partial Points

This problem has partial points:

• Correctly solving the dataset where $ 3≦N≦8 $ earns $ 15 $ points.
• Correctly solving the dataset where $ 3≦N≦2,000 $ earns an additional $ 55 $ points.
• Correctly solving the dataset where $ 3≦N≦10^5 $ earns an additional $ 70 $ points, totaling $ 140 $ points.

Sample Explanation 1

The sum of the volumes of the $ 6 $ cups is $ 24 $. 

Sample Explanation 2

Rectangles with the same width and height are distinguished when arranged.

见题面 Input 部分

见题面 Output 部分