갈라테아의 식단
시간 제한1초메모리 제한512 MB
N가지 사탕 종류 중에서 M일 동안 하루에 하나씩 고르되, 일부 날의 종류가 미리 정해져 있고 연속한 두 날에 같은 종류를 먹지 않는 경우의 수를 1,000,000,007로 나눈 나머지로 구한다.
문제
이 세상에는 1번부터 N번까지 번호가 붙은 N종류의 사탕이 있다. 갈라테아는 M일 연속으로 매일 사탕 하나를 먹는다. 같은 종류의 사탕을 이틀 연속으로 먹으면 지루하기 때문에 갈라테아는 그렇게 먹지 않는다.
갈라테아는 미스 갤럭시 대회에 나갈 계획이므로 다이어트를 해야 한다. 목표를 지키기 위해 미용사가 갈라테아에게 특정 식단을 제안한다. 정확히는, 1 ≤ i ≤ K인 각 i에 대해 갈라테아는 Ai번째 날에 Bi종류의 사탕을 먹는다. 나머지 날, 즉 미리 정해지지 않은 날에는 아무 종류의 사탕이나 자유롭게 먹을 수 있다.
갈라테아의 조건, 즉 이틀 연속으로 같은 종류의 사탕을 먹지 않는다는 조건을 만족하는 식단의 가짓수를 구하시오. 두 식단은 어떤 날에 갈라테아가 먹는 사탕의 종류가 다르면 서로 다른 식단이다. 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
입력
첫째 줄에 사탕 종류의 수, 날의 수, 사탕 종류가 미리 정해진 날의 수를 나타내는 세 정수 N M K가 주어진다 (1 ≤ N ≤ 1,000,000,000; 1 ≤ M ≤ 10^18; 1 ≤ K ≤ min(M, 10,000)).
다음 K개 줄에 각각 미리 정해진 사탕 종류를 나타내는 두 정수 Ai Bi가 주어진다 (1 ≤ Ai ≤ M; 1 ≤ Bi ≤ N). Ai는 증가하는 순서로 주어진다. 즉, 모든 1 ≤ i < j ≤ K에 대해 Ai < Aj이다.
출력
갈라테아의 조건을 만족하는 식단의 가짓수를 한 줄에 출력한다. 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.