问题描述

给定一棵包含 $N$ 个节点的树。每个节点都被编号为 $1, 2, ..., N$，第 $i$ 条边连接了节点 $a_i, b_i$。

考虑在树的每个节点上写入整数 $1, 2, ..., N$ 中的一个值。设节点 $i$ 上的值为 $c_i$。

然而，如果相邻的节点 $u, v$ 存在边 $(u, v)$，那么必须满足条件 $|c_u - c_v| ≤ 2$。

请计算有多少种这样的写入方式，输出结果对 $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