問題文

$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