덧셈 프로그램

프로그램 P의 처음에 크기 $N$의 배열 $A$가 선언되어 있고, 배열 값 $A[1], A[2], \dots, A[N]$이 모두 0으로 초기화되어있다.

프로그램 P에는 $M$ 개의 명령이 있다. $i$ 번째 명령은 다음과 같다.

여기서, $a := b$는 $a$에 값 $b$를 대입하는 연산이다.

우리는 P를 총 $L$ 번 독립적으로 실행할 것이다. 이때, $j$ 번째 실행에서 각각 $K_j$ 개의 입력값 $U_{j, k}, V_{j, k}$가 주어지고, 이 입력값을 이용해 위의 명령 이전에 다음과 같이 배열의 초기값이 주어진다:

각 $j$ 번째 실행에서, 주어지는 $U_{j, k}$는 모두 다르다. 또, $U_{j, k}$로 주어지지 않는 $i$에 대해서 $A[i] := 0$임에 주의하자.

프로그램 P의 각각의 실행 뒤, $A[1]$의 값을 구하자.

입력 형식

첫 줄에 배열의 크기를 나타내는 $N$, 덧셈 연산을 나타내는 정수 $M$, 실행 횟수를 나타내는 정수 $L$이 공백으로 구분되어 주어진다. ($1 \le N, M, L \le 250\,000$)

이어지는 $M$개 줄의 $i$ 번째 줄에는 $i$ 번째 명령을 정의하는 상수를 나타내는 두 정수 $X_i$와 $Y_i$가 주어진다. ($1 \le X_i, Y_i \le N$)

프로그램의 $L$ 번의 실행을 나타내는 줄들이 순서대로 주어진다. 이 중 $j$ 번째 실행을 나타내는 줄들의 첫 줄에는 입력값의 개수를 나타내는 정수 $K_j$가 주어진다. ($1 \le K_j \le N$) 이어지는 $K_j$ 개의 줄의 $k$ 번째 줄에는 입력값을 나타내는 두 정수 $U_{j, k}$와 $V_{j, k}$가 주어진다. ($1 \le U_{j, k} \le N, 1 \le V_{j, k} \le 1\,000\,000\,000$)

입력값의 총개수인 $\sum K_j$은 $250\,000$ 이하이다.

출력 형식

$L$ 개 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 프로그램의 $i$ 번째 실행 이후, $A[1]$의 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 1

3 7 2
3 3
3 1
1 2
1 1
1 3
2 1
1 2
2
2 3
3 8
3
1 2
2 6
3 7

47
70

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설