시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 512 MB 369 122 91 38.075%

문제

1부터 N까지의 번호가 부여된 N개의 정점과 N-1개의 간선으로 구성된 트리가 있다. 이 트리의 루트는 1번 정점이며, 임의의 한 정점과 다른 정점 사이의 경로가 반드시 한 개 존재한다.

트리의 각 정점은 특정 색깔을 가지고 있다. 편의상 색깔은 1 이상 C 이하의 자연수로 표현된다. 이때, 질의 f(v,c)를 다음과 같이 정의하자.

f(v, c) : 정점 v가 루트인 부트리(sub-tree)에서 색깔이 c 이하인 정점의 개수

M개의 질의 f(vi, ci)가 주어질 때, 각 질의에 대한 답을 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정점의 수를 나타내는 N(1 ≤ N ≤ 2×105), 질의의 개수를 나타내는 M(1 ≤ M ≤ 2×105), 정점의 색깔 종류를 나타내는 C(1 ≤ C ≤ N)가 공백 하나를 사이에 두고 차례로 주어진다.

두 번째 줄에는 각 정점의 색깔을 나타내는 N개의 정수가 공백으로 구분되어 순서대로 주어진다. 첫 번째 수는 1번 정점의 색깔이며, ..., N 번째 수는 N번 정점의 색깔이다.

세 번째 줄부터 N-1개의 줄에 걸쳐서 트리를 이루는 각 간선의 정보가 주어진다. 각 간선의 정보는 해당 간선을 이루는 서로 다른 두 정점의 번호로 구성된다. 각 정점의 번호는 1 이상 N 이하의 자연수이다.

이후, 이어서 M개의 줄에 걸쳐서 i번째 줄에 i번째 질의의 정보 vi, ci가 공백으로 구분되어 주어진다. vi는 1 이상 N 이하의 정점 번호를 나타낸다. ci는 1 이상 C 이하의 색깔 정보를 나타낸다.

출력

M개의 질의에 대한 정답을 모두 더한 뒤, 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5 5 3
1 2 1 3 3
1 2
2 3
3 4
4 5
1 1
1 3
3 2
4 3
5 3

예제 출력 1

11

예제 입력 2

4 2 2
1 2 2 2
1 2
1 3
1 4
1 1
1 2

예제 출력 2

5