AT_ddcc2017_final_d なめらかな木

给定一棵有 $N$ 个顶点的树。每个顶点的编号为 $1, 2, \ldots, N$，第 $i$ 条边连接着顶点 $a_i$ 和 $b_i$。 现在需要将整数 $1, 2, \ldots, N$ 各写一次，分别写在这些顶点上。假设顶点 $i$ 被写的值是 $c_i$。 但是，若顶点 $u$ 和 $v$ 是相邻的（即存在边 $(u, v)$），则必须满足 $|c_u - c_v| \leq 2$。 请问有多少种不同的写法？请将结果对 $1000000007 = 10^9 + 7$ 取模后输出。

输入将以下列格式由标准输入给出。 > $N$ > $a_1$ $b_1$ > $a_2$ $b_2$ > \vdots > $a_{N-1}$ $b_{N-1}$

请输出答案。

### 限制条件 - $1 \leq N \leq 50$ - $1 \leq a_i, b_i \leq N$ - 输入保证形成一棵树 ### 样例说明 1 必须在顶点 $1$ 上写入 $3$。 由 ChatGPT 5 翻译