問題文

$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$
• 入力は木になっている

入力例 1Copy

5
1 2
1 3
1 4
1 5

出力例 1Copy

24

頂点 $1$ に $3$ を書き込む必要があります。

入力例 2Copy

6
1 2
1 3
1 4
1 5
1 6

出力例 2Copy

0

入力例 3Copy

4
1 2
2 3
3 4

出力例 3Copy

12

入力例 4Copy

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

出力例 4Copy

48