Our story - Chuyen chung minh


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

She is the one who, with just a few words, let the world finds out the distance between the two of us.

The moment came when everyone knew all three of us. Neither He nor She could stay calm, words slipped out, whether to make the world believe us, or just to convince ourselves that we were still holding it together. But in the end, no one gave even a thoughtful nod. Had we gone too far? Should we have stopped before we even began? Should we change things while there's still time?

As the story unfolds...

They chose to keep waiting for new stories. The tale of the three of us seemed to keep gaining new characters. They put forward a list of \(N\) other people, people who stand in front of the cameras or behind the scenes, and each one of them is governed by two things: \(a_i\) coins kept in the dark, and \(b_i\) hidden stories (together called their influence).

She ranks these people by their influence, in increasing order. And a person's rank is the number of people whose influence is strictly less than theirs, \(+\ 1\).

The world keeps wondering, in a given ranking, how many people have a rank whose value equals the influence of the one chosen!

And they keep producing different versions of the ranking. For each person, they choose to define their influence as either their coin count or their hidden-story count, giving rise to \(2^N\) possible versions in total. Each version produces its own ranking, and the number of chosen people in that version is called \(g\).

They want to find the sum of \(g\) over all versions.

Input

  • The first line contains a positive integer \(N \ (2 \le N \le 2 \times 10^5)\);
  • The next \(N\) lines, each containing two integers \(a_i, b_i \ (1 \le a_i < b_i \le N)\).

Output

  • A single integer as the answer to the problem, taken modulo \(10^9+7\).

Scoring

  • Subtask 1 (50%): \(N \le 18\).
  • Subtask 2 (50%): No additional constraints.

Example

Example 1

input

3
1 2
2 3
1 3

output

16
Example 2

input

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

output

4752

Comments

There are no comments at the moment.