Scarf Signals at Dawn
At dawn, cats sit in a line at positions . The cat at position wears a scarf with label and has a fish reward worth .
Each cat wakes exactly once. Their wake order is chosen uniformly at random from all possible orders. Once awake, a cat remains awake.
When the cat at position wakes, it looks for both of the following cats:
- the nearest currently awake cat at a position ;
- the nearest currently awake cat at a position .
If either such cat does not exist, the waking cat earns nothing. If both exist and their scarf labels are equal, the waking cat earns fish. Otherwise, it earns nothing. The scarf label of the waking cat itself does not affect this decision.
Find the expected total amount of fish earned by all cats.
Input
The first line contains an integer (), the number of cats.
The next lines describe the cats from left to right. The -th of these lines contains two integers and (, ), the scarf label and fish reward of the cat at position , respectively.
Output
Let the expected total fish reward be the reduced fraction . Print the integer
where is the multiplicative inverse of modulo . The constraints guarantee that this inverse exists.
Samples
Sample 1
Input
3 1 4 2 6 1 9
Output
2
The expected total reward is fish.
Sample 2
Input
5 1 4 2 7 1 5 2 3 1 6
Output
499122182
The expected total reward is , whose required representation is .