問題文

クリスマスツリーを持った青いうさぎと赤いうなぎがぶつかってしまい、二つのツリーがこんがらがってしまいました。

N 頂点からなるグラフが与えられます。 頂点には 1 〜 N の番号がつけられています。 辺は N*2-2 本あり、i 番目の辺は頂点 A_i と頂点 B_i を繋いでいます。

このグラフの辺を赤と青に塗り分ける方法であって、赤い辺のみからなるグラフも青い辺のみからなるグラフも木になるようなものは何通りあるでしょうか？

答えは非常に大きくなることがあるので、10^9+7 で割ったあまりを求めてください。

制約

• 4 \leq N \leq 104
• 1 \leq A_i,B_i \leq N
• 自己ループや多重辺は存在しない
• 問題文中の条件を満たす塗り分け方が少なくとも 1 通り以上存在する

採点

テストケースは 01.txt 〜 10.txt の 10 個あり、テストケースに 1 つ正解するごとに 10 点が与えられます。

この問題ではテストケースが公開されており、こちらからダウンロードすることができます。

入力例 1

4
1 2
1 3
1 4
2 3
2 4
4 3

出力例 1

12

このケースでは以下の 12 通りの塗り分け方があります。

図：塗り分け方の一覧