← 返回题目列表

AtCoder · ddcc2017_final_d

D. 光滑木材

中文机器翻译题面 查看原题

配点 : 1100 点

問題文

N 给出一棵顶点树。 顶部的数字 附上 1, 2, ..., N ,i 第一条边是顶点 a_i, b_i 已连接。

树顶部的整数 1, 2, ..., N 分别 考虑一一写 1 。 顶点 写入 i 的值 c_i 。

然而,顶点 u, v 是相邻的,即边缘 如果 (u, v) 存在,则 必须满足 |c_u - c_v| ≦ 2 。(10:53) 固定变量名称

像这样的东西你可以有多少种写法?1000000007 = 10^9 + 7 求余数。

制約

  • 1 ≦ N ≦ 50
  • 1 ≦ a_i, b_i ≦ N
  • 输入是一棵树

入力

输入是按以下格式从标准输入给出的。

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}

出力

请输出得到的答案。


入力例 1

5
1 2
1 3
1 4
1 5

出力例 1

24

頂点 1 至 必须写 3 。


入力例 2

6
1 2
1 3
1 4
1 5
1 6

出力例 2

0

入力例 3

4
1 2
2 3
3 4

出力例 3

12

入力例 4

7
1 3
2 3
4 3
5 4
5 6
5 7

出力例 4

48