Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 150 点
問題文
夏祭りには N 種類の屋台が鳥居から神社の拝殿に通じる長さ 2N の道にかけて並んでいます. この道は 2N 個の区画に等間隔に分割されていて,鳥居から数えて k 番目の区画を区画 k と呼びます.また, i 番目の屋台を屋台 i と呼びます.
各屋台は,店を開くためにあらかじめ神社に営業許可を取った結果,今年はどの屋台もちょうど 2 つの区画を使ってよいことになりました. 具体的には,屋台 i には,区画 A_{i} と区画 B_{i} の使用許可が下りました. 整数A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} はすべて異なり,すべての i について A_{i} \lt B_{i} が成立します. 屋台 i は,神社に営業許可を出された区画 A_{i} と B_{i} を行き来する時に, A_{i} \leq p \leq B_{i} を満たすすべての整数 p について,区画 p を一時的に通過する必要があります. このような区画 p を「屋台 i の通路上に存在する」と言います.
屋台 x と屋台 y について,二つの屋台両方の通路上に存在する区画がある場合,商売するうえで支障が生じるかもしれません. そこで,神社は屋台同士の関係を把握するために,すべての x \neq y である屋台の組 x, y について,二つの屋台両方の通路上に存在する区画がある場合,頂点 x と頂点 y を無向辺で結んだ頂点数 N のグラフを作成しました. platypusくんは,夏祭りを最大限に楽しむために,裏ルートでこのグラフを入手しましたが,なんとこのグラフは連結な無向木でした. そこで,この木から元の A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} を復元しようと思いました.
この木から,元の整数の組 (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) として考えられるものは何通りあるかを答えるプログラムを作成しなさい. ただし,答えは非常に大きくなる可能性があるため, 1000000007 で割った余りを出力しなさい.
制約
すべてのテストケースは以下の制約を満たします.
- 2 \leq N \leq 200000
- 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
- 与えられるグラフは連結な無向木である.
入力
入力は以下の形式で標準入力から与えられる.
N u_{1} v_{1} u_{2} v_{2} : u_{N-1} v_{N-1}
- 1行目には整数 N が書かれている.これは,platypusくんが入手したグラフの頂点数を表している.
- 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている.これは,グラフの i 番目の辺は頂点 u_{i} と v_{i} を結んでいることを表している.
出力
標準出力に,与えられたグラフと同じグラフが作られるような (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) が何通り存在するかを 1000000007 で割った余りを一行で出力せよ. ただし,platypusくんの勘違いなどによって 0 通りの入力ケースも存在しうることに留意せよ.
入力例 1
3 1 2 1 3
出力例 1
8
この場合,考えられる (A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) は以下の 8 通りあります.
(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) = (1,2,4,5,3,6) (1,2,4,6,3,5) (1,4,2,5,6,3) (1,4,2,6,5,3) (2,1,4,5,3,6) (2,1,4,6,3,5) (2,4,1,5,6,3) (2,4,1,6,5,3)
すべての i について A_{i} \lt B_{i} という制約が存在することに注意しなさい.
入力例 2
7 1 2 1 3 1 4 2 5 3 6 4 7
出力例 2
0
このようなグラフができる (A_{1}, A_{2}, ..., A_{7}, B_{1}, B_{2}, ..., B_{7}) は存在しないため,求める答えは0です.