Dipingere il granaio#10516
Il contadino John possiede una grande fattoria con granai, alcuni dei quali sono già stati dipinti, mentre gli altri non lo sono ancora. Il contadino John vuole dipingere tutti i granai rimanenti, ma ha a disposizione solo tre colori. Inoltre, la sua mucca preferita Bessie si confonde se due granai direttamente collegati tra loro sono dipinti dello stesso colore, quindi il contadino John vuole evitare questa situazione.
In quanti modi può il contadino John dipingere i restanti granai non ancora dipinti?
Nella prima riga sono contenuti due numeri interi n~(1 \le n \le 10^5) e k~(0 \le k \le n), che indicano rispettivamente il numero di granai nella fattoria e il numero di granai già dipinti.
Nelle successive n - 1 righe sono contenuti due numeri interi e y~(1 \le x, y \le n, x \neq y), che descrivono un percorso che collega direttamente i granai e .
Nelle successive righe sono contenuti due numeri interi e c~(1 \le b \le n, 1 \le c \le 3), che indicano che il granaio è dipinto del colore .
Calcola il numero di modi validi per dipingere i granai rimanenti modulo 10^9 + 7, in modo che nessuna coppia di granai direttamente collegati sia dipinta dello stesso colore.
Esempio 1