An Animal Contest 6 P5 - Rock Painting

View as PDF

Submit solution

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

Problem type

Kyriakos Grizzly got bored from exercising so he decided to paint his rock collection! His collection consists of N rocks which he lays across the ground in a row, numbered 1 to N from left to right. He also has C colours of paint which he will use to paint the rocks. Exactly M of his N rocks have already been painted (with one of the C 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 c that appears at least once, find the index of the leftmost rock i with colour c and the index of the rightmost rock j with colour c. The score is the sum of j-i for all c.

If each rock (that hasn't been painted) is painted randomly with a colour from 1 to C, what is the expected value of the score?


1 \le N, C \le 10^9

0 \le M \le \min(N, 2 \times 10^5)

1 \le r_i \le N

1 \le c_i \le C

All r_i will be distinct.

Subtask 1 [30%]

1 \le N \le 2 \times 10^5

Subtask 2 [20%]

M = 0

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, N, C, and M.

The next M lines will contain two space-separated integers, r_i and c_i, indicating that rock r_i has already been painted with colour c_i.

Output Specification

Output one integer, the expected value of the score modulo 10^9 + 7. More specifically, if the expected value is \frac{x}{y}, output xy^{-1} \pmod{10^9 + 7}.

Sample Input 1

5 2 3
1 2
3 1
5 2

Sample Output 1


Sample Input 2

7 4 3
2 4
5 2
4 1

Sample Output 2



There are no comments at the moment.