시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 8 6 6 100.000%

문제

설레는 크리스마스가 얼마 남지 않았다. 하지만 슬프게도 여친이 없는 셈터는 외로움을 달래기 위해 크리스마스 트리나 장식하려고 한다. 트리에는 전구를 끼울 수 있는 소켓들이 달려 있다. 화려한 것을 좋아하는 셈터는 소켓에 색전구를 끼워서 반짝반짝 빛나게 만들고 싶다.

트리에 달려 있는 소켓 개수 V가 주어진다. 각 소켓들 사이에는 전선들이 연결되어 있는데, 1번 소켓에서부터 전선을 타고 모든 소켓까지 전기가 공급되도록 전선 V-1개로 연결되어 있다. V는 1000 이하의 자연수이다.

각 소켓에 대해 빨강, 초록, 파랑(R, G, B) 세 종류의 색전구 중 하나를 끼울 수 있다. i번 소켓에 빨강, 초록, 파랑 전구를 끼우는 데 Ri, Gi, Bi의 비용이 든다. 단, 초록 전구가 달린 소켓끼리는 직접 연결되지 않고, 파랑 전구가 달린 소켓에는 초록 전구가 달린 소켓만 직접 연결된다. 모든 비용은 10 이하이다.

셈터는 전구를 모두 끼우는 데 드는 비용이 K ≤ 10로 나누어 떨어지게 하고 싶다. 위의 모든 조건을 만족하면서 모든 소켓에 전구를 끼우는 방법의 수를 구하는 프로그램을 작성하시오. 단, 답이 매우 커질 수 있으므로 Q ≤ 1000로 나눈 나머지를 출력하시오.

입력

첫째 줄에는 정수 V, Q, K가 공백으로 구분되어 주어진다.

두 번째 줄부터 V-1개의 줄에는 소켓 번호 a, b가 공백으로 구분되어 주어진다. 이는 a와 b를 잇는 전선이 존재한다는 것을 의미한다.

그 다음 V개의 줄에는 각 소켓에 빨강, 초록, 파랑 전구를 끼우는 데 드는 비용 Ri, Gi, Bi 가 주어진다.

출력

총 비용이 K로 나누어 떨어지도록 주어진 트리의 모든 소켓에 전구를 끼우는 방법의 수를 Q로 나눈 나머지를 출력한다.

예제 입력

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

예제 출력

2

예제 입력 2

7 997 10
1 2
2 3
3 4
1 5
4 6
4 7
7 3 8
0 2 4
7 2 9
0 2 9
1 4 1
5 9 0
0 7 9

예제 출력 2

8

힌트