配点 : 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