누가 크리스마스 소리를 내었는가

크리스마스가 얼마 남지 않아 셈터는 트리를 장식하기로 했다. 트리에는 전구를 끼울 소켓이 $V$개 달려 있고, 소켓끼리는 전선 $V-1$개로 이어져 있다. 1번 소켓에서 전선을 따라가면 모든 소켓에 전기가 닿는다. 즉 소켓과 전선은 트리 구조를 이룬다.

각 소켓에는 빨강($R$), 초록($G$), 파랑($B$) 중 한 가지 색의 전구를 하나씩 끼운다. $i$번 소켓에 빨강 전구를 끼우면 $R_i$, 초록 전구를 끼우면 $G_i$, 파랑 전구를 끼우면 $B_i$의 비용이 든다. 배치는 다음 두 조건을 지켜야 한다.

• 초록 전구가 달린 소켓 두 개는 전선으로 직접 이어지지 않는다.
• 파랑 전구가 달린 소켓에 직접 이어진 소켓에는 모두 초록 전구가 달려 있다.

모든 소켓의 비용을 더한 값이 $K$의 배수가 되는 배치가 몇 가지인지 세어라. 답이 매우 커질 수 있으므로 $Q$로 나눈 나머지를 출력한다. 소켓 하나라도 전구 색이 다르면 서로 다른 배치로 센다.

$1 \le V \le 1000$, $1 \le Q \le 1000$, $1 \le K \le 10$, $0 \le R_i, G_i, B_i \le 10$이다.

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

다음 $V-1$개의 줄에는 전선으로 이어진 소켓 번호 $a$와 $b$가 공백으로 구분되어 주어진다.

그다음 $V$개의 줄에는 $i$번 소켓의 비용 $R_i$, $G_i$, $B_i$가 순서대로 주어진다. 소켓 번호는 1번부터 $V$번까지다.

전체 비용이 $K$로 나누어떨어지는 배치의 수를 $Q$로 나눈 나머지를 한 줄에 출력한다.