Who made the Christmas sound

Christmas is close, so Semter decorates a tree. The tree carries $V$ sockets for bulbs, and the sockets are joined by $V-1$ wires. Starting at socket 1 and following the wires, electricity reaches every socket, so the sockets and the wires form a tree.

Each socket takes exactly one bulb, red ($R$), green ($G$), or blue ($B$). A red bulb in socket $i$ costs $R_i$, a green bulb costs $G_i$, and a blue bulb costs $B_i$. An arrangement must satisfy two conditions.

• No wire directly joins two sockets that both hold a green bulb.
• Every socket directly joined to a socket holding a blue bulb holds a green bulb.

Count the arrangements whose total cost over all sockets is a multiple of $K$. The count can be very large, so print it modulo $Q$. Two arrangements are different when at least one socket holds a bulb of a different color.

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

The first line has $V$, $Q$, and $K$, separated by spaces.

Each of the next $V-1$ lines has two socket numbers $a$ and $b$, separated by a space, meaning a wire joins socket $a$ and socket $b$.

Each of the following $V$ lines has the costs $R_i$, $G_i$, and $B_i$ of socket $i$, in that order. Sockets are numbered 1 to $V$.

Print one line with the number of arrangements whose total cost is divisible by $K$, taken modulo $Q$.