题目翻译

给定 $N$ 个顶点的树，每个顶点编号为 $1,2,\dots,N$。每个顶点上都写上整数 $1,2,\dots,N$ 中的数，顶点 $i$ 上写的数为 $c_i$，不同顶点上写的数必须不同。

如果顶点 $u,v$ 邻接，也就是存在边 $u,v$，那么必须满足 $|c_u-c_v|\le2$。

满足上述条件的写数方案有多少种，请求出方案数模 $1000000007=10^9+7$ 的值。

数据范围

• $1\le N\le 50$
• $1\le a_i, b_i \le N$
• 可以保证输入构成一棵树

输入

输入按照以下格式。第一行输入一个 $N$，下面的 $N-1$ 行，每行输入两个整数 $a_i b_i$，表示树中的一条边。

输出

如上，输出种类数模 $10^9+7$ 的值。

测试用例

测试用例 1

输入

5
1 2 
1 3
1 4
1 5

输出

24

解说

顶点 $1$ 只能写 $3$。

测试用例 2

输入

6
1 2
1 3
1 4
1 5
1 6

输出

0

测试用例 3

输入

4
1 2
2 3
3 4

输出

12

测试用例 4

输入

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

输出

48