Scarf-Matched Extremes
A row of cushions is prepared for a yarn festival. The cats are placed on the cushions according to a uniformly random permutation, so each of the possible orders is equally likely.
Every contiguous segment of at least cushions is inspected. Because all cats have distinct agility values, each such segment has exactly one least-agile cat and exactly one most-agile cat.
A segment is awarded one fish if its least-agile cat and its most-agile cat have the same yarn color. Each qualifying segment is awarded separately, including segments that overlap or contain other qualifying segments.
Compute the expected total number of fish awarded.
Input
The first line contains an integer (), the number of cats.
The next lines describe the cats. The -th line contains two integers and (), representing the agility and yarn color of the -th cat, respectively.
Output
Print one integer: the expected number of fish awarded, modulo .
More precisely, if the expected value is written as a reduced fraction , print
Samples
Sample 1
Input
2 10 7 20 7
Output
1
The two cats always form the only eligible segment, and their yarn colors match. Exactly fish is awarded.
Sample 2
Input
3 4 1 9 2 15 1
Output
666666673
The expected number of awarded fish is . Its required residue modulo is .