| 问题描述 |
|---|
给定一棵具有 n 个结点的树和 3 种颜色，你需要对树上的所有结点进行染色，并且保证在染色后，任意两个相邻结点的颜色均不相同。 罗少认为这太简单了，于是提前给一些点染上了色，请问，这棵树最后的染色结果有多少种。 两种染色结果认为是不同的当且仅当两种结果中至少存在一个点的颜色不同。 |
| 输入描述 |
第一行是一个正整数 n 表示结点数量。（1 ≤ n ≤ 1e5） 接下来 n - 1 行，每行两个结点编号 x 和 y 表示他们之间有一条边。（1 ≤ x、y ≤ n） 最后一行 n 个数字分别表示每个结点的初始状态，这些数字只会是 [0, 1, 2, 3] 中的一个，若为 0 表示该点未染色，否则表示该点已经染上了对应数字的颜色。 |
| 输出描述 |
在一行中输出这棵树最后的染色结果有多少种。 由于答案可能很大，所以你只需要输出它对1000000007取余之后的结果。 |
| 样例输入复制样例 |
3 1 2 2 3 0 0 0 |
| 样例输出 |
12 |
| 相关 |