Problem Description

――Gather the scattered stone tablets across the world. Bring order to chaos. Only then will the light be granted――

Takahashi's playthrough of the puzzle RPG "Chaos of the Snuke World" is approaching its climax.

The setting of this game is an empire that flourished in an ancient magical civilization. Twelve hundred years ago, a coup d'état against the emperor who imposed a reign of terror led the citizens to seize power. They decided to disperse the magical stone tablets, which were the source of the emperor's power, across the land to prevent the rise of such a ruler in the future. Ironically, this act led to cracks in the country's unity through magic, and both the center and the periphery were destroyed without distinction, and the locations of the stone tablets were forgotten.

The protagonist is a boy who dreams of the revival of the prosperous magical empire. The boy, controlled by Takahashi, traveled through villages, forests, and caves, and finally collected all the stone tablets.

There are a total of $ N $ stone tablets, and the front of the $ i $ -th tablet has the integer $ A_i $ written on it, while the back has the integer $ B_i $ written on it.

The boy's task now is to arrange the stone tablets on the platform at the innermost part of the ruined palace. However, this is where the final and greatest challenge lies.

The platform can arrange the stone tablets in a single row. The boy can arrange the stone tablets in any order and with either side facing up. When the boy finishes arranging all the stone tablets, an ancient curse placed by the citizens who established the regime may activate, flipping the stone tablets over. Each tablet has exactly a 50% chance of being flipped.

After that, the boy can swap adjacent stone tablets as many times as he wants. If the boy can arrange the stone tablets so that the integers written on the upper sides are non-decreasing from left to right, the empire where people lived in prosperity will be revived, and the boy's dream will come true. However, if he struggles with this operation... ancient magic will be activated, and the stone tablets will scatter again!

If the stone tablets scatter, the boy will have to collect them again. Takahashi, who wants to clear the game quickly, decided to arrange the stone tablets on the platform so that the expected number of swap operations required is minimized.

Takahashi is tired from playing too much of the game and has sore eyes. For Takahashi's sake, please find the minimum value of the expected number of swap operations multiplied by $ 2^N $ (it can be proven that this value is an integer) modulo $ 10^9+7 $.

Input Format

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

$ N $ $ A_1 $ $ B_1 $ : $ A_N $ $ B_N $

Output Format

Output the minimum value of the expected number of swap operations multiplied by $ 2^N $ modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4
1 5
2 6
8 2
3 4

Sample Output #1

36

Sample Input #2

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

Sample Output #2

224

Notes/Hints

Constraints

• $1\leq\ N\leq\ 10^5$
• $1\leq\ A_i,B_i\leq\ 2N(1\leq\ i\leq\ N)$
• All inputs are integers

Sample Explanation 1

When the stone tablets are arranged in the order of 4, 1, 2, 3, the expected number of swap operations is $ 2.25 $. Output $ 36 $, which is $ 2^4 $ times this value.

见题面 Input 部分

见题面 Output 部分