問題文

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

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