塗り木 Python3編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

木が与えられます。あなたは木の各ノードを 3 色のうち好きな色で塗りつぶすことができます。隣り合うノードが同じ色にはならないような塗り方は何通りありますか？

入力される値

N
S_1 T_1
S_2 T_2
...
S_{N-1} T_{N-1}

・ 1 行目に、木のノード数 N が与えられます。
・ 2 行目から N 行目にかけて、辺の情報が与えられます。ノード S_i とノード T_i がつながっています。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 隣り合うノードが同じ色にはならないような塗り方の個数を答えてください。答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。