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?
Constraints
~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 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
5
Sample Input 2
7 4 3
2 4
5 2
4 1
Sample Output 2
210937509
Comments
it involves nasty math in the description and is confusing
You'll have to get used to modular arithmetic sooner or later in competitive programming, it's quite common as a way to work with large numbers and fractions. See this blogpost for details.
That said, this is a 20-point problem, so probably try something else instead.
this question seems supa hard
hello
hi