시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB100454162.121%

문제

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

트리에 달려 있는 소켓 개수 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로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

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

출처

University > 서강대학교 > 2017 Sogang Programming Contest > Champion D번

  • 데이터를 추가한 사람: alex9801
  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: lvalue