시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 13 4 4 36.364%

문제

There are N types of candy in this world, indexed 1 to N. For M consecutive days, Galatea will eat one candy every day. Eating two candies of the same type for two consecutive days is boring, so Galatea will avoid it.

As Galatea plans to participate in the Miss Galaxies contest, she should go on a diet. To comply with her goal, her beautician suggests Galatea to go on a specific diet. More precisely, Galatea will eat a candy of type Bi on the Ai-th day for 1 ≤ iK. She is free to eat any type of candy on the other days (outside the previously predetermined days).

Determine the number of possible eating configurations (diets) which satisfies Galatea’s requirement (not eating two candies of the same type for any two consecutive days). Two eating configurations are different if there is a day which Galatea eats a different type of candy on that day. Since the output might be a very large number, output the remainder of the number when divided by 1,000,000,007.

입력

The first line contains three integers: N M K (1 ≤ N ≤ 1,000,000,000; 1 ≤ M ≤ 1018; 1 ≤ K ≤ min(M, 10,000)) in a line denoting the number of candy types, the number of days, and the number of days which the candy type is predetermined. The next K following lines, each contains two integers: Ai Bi (1 ≤ AiM; 1 ≤ BiN) denoting the predetermined candy types. Ai is guaranteed to be given in increasing order; in other words, Ai < Aj, for all 1 ≤ i < jK.

출력

The output contains the number of possible eating configurations that satisfies Galatea’s requirement, in a line. Since the output might be a very large number, output the remainder of the number when divided by 1,000,000,007.

예제 입력 1

3 4 2
1 1
4 2

예제 출력 1

3

On the first sample, there are three possible solutions:

Solution 1:

  • Eat the first type of candy on the first day
  • Eat the second type of candy on the second day
  • Eat the third type of candy on the third day
  • Eat the second type of candy on the fourth day

Solution 2:

  • Eat the first type of candy on the first day
  • Eat the second type of candy on the second day
  • Eat the first type of candy on the third day
  • Eat the second type of candy on the fourth day

Solution 3:

  • Eat the first type of candy on the first day
  • Eat the third type of candy on the second day
  • Eat the first type of candy on the third day
  • Eat the second type of candy on the fourth day

예제 입력 2

3 4 2
1 1
2 1

예제 출력 2

0

On the second sample, Galatea will avoid eating the same type of candy on two consecutive days (the first and second day). Since in the first and second days, her beautician suggests her to eat the same type of candies, there are no ways to satisfy Galatea’s requirement.