D - なめらかな木

Time Limit: 2 sec / Memory Limit: 256 MB

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

頂点 13 を書き込む必要があります。


入力例 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