AT_ddcc2017_final_d なめらかな木

[problemUrl]: https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_d $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_{N-1} $ $ b_{N-1} $

求めた答えを出力してください。

### 制約 - $ 1\ ≦\ N\ ≦\ 50 $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N $ - 入力は木になっている ### Sample Explanation 1 頂点 $ 1 $ に $ 3 $ を書き込む必要があります。