## An Animal Contest 6 P5 - Rock Painting

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type

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.

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