Kyriakos Grizzly got bored from exercising so he decided to paint his rock collection! His collection consists of rocks which he lays across the ground in a row, numbered
to
from left to right. He also has
colours of paint which he will use to paint the rocks. Exactly
of his
rocks have already been painted (with one of the
colours), in which case they will not be painted again. Kyriakos, being very artistic, realizes that his collection will be more beautiful if each colour used is more spread out. Thus, he will assign his collection a score in the following way:
For every colour
that appears at least once, find the index of the leftmost rock
with colour
and the index of the rightmost rock
with colour
. The score is the sum of
for all
.
If each rock (that hasn't been painted) is painted randomly with a colour from to
, what is the expected value of the score?
Constraints
All will be distinct.
Subtask 1 [30%]
Subtask 2 [20%]
Subtask 3 [50%]
No additional constraints.
Note: You must pass subtasks 1 and 2 in order for this subtask to be run.
Input Specification
The first line will contain three space-separated integers, ,
, and
.
The next lines will contain two space-separated integers,
and
, indicating that rock
has already been painted with colour
.
Output Specification
Output one integer, the expected value of the score modulo . More specifically, if the expected value is
, output
.
Sample Input 1
5 2 3
1 2
3 1
5 2
Sample Output 1
5
Sample Input 2
7 4 3
2 4
5 2
4 1
Sample Output 2
210937509
Comments