AT_abc160_f [ABC160F] Distributing Integers

[problemUrl]: https://atcoder.jp/contests/abc160/tasks/abc160_f $ 1 $ から $ N $ までの番号が付けられた $ N $ 個の頂点を持つ木があります。この木の $ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 $ k=1,...,N $ に対して、以下の問題を解いてください。 - 以下の手順に従って,木の各頂点に整数を書くことを考える。 - まず、頂点 $ k $ に $ 1 $ を書く。 - $ 2,...,N $ を順番に頂点に書く。書き込む頂点は、次のように決める。 - まだ整数が書かれていない頂点であって、整数が書かれた頂点に隣接しているものを選ぶ。このような頂点が複数存在する場合は、その中からランダムに選ぶ。 - 整数の書き方として考えられるものの数を $ 10^9+7 $ で割ったあまりを求めよ。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - 与えられるグラフは木である ### Sample Explanation 1 この入力中のグラフは以下のようなものです。 !\[図\](https://img.atcoder.jp/ghi/1c88b0eb716ba399b1c5d6565ab62337.png) $ k=1 $ に対する問題において、以下のように $ 2 $ 通りの整数の書き方が考えられます。 - 頂点 $ 1,2,3 $ に、それぞれ $ 1,2,3 $ を書く - 頂点 $ 1,2,3 $ に、それぞれ $ 1,3,2 $ を書く ### Sample Explanation 2 この入力中のグラフは以下のようなものです。 !\[図\](https://img.atcoder.jp/ghi/c47c7798f88e7bfec30fbd664dc9ad50.png) ### Sample Explanation 3 この入力中のグラフは以下のようなものです。 !\[図\](https://img.atcoder.jp/ghi/e9c09403f8d96ae4e679a226993defa6.png) ### Sample Explanation 4 この入力中のグラフは以下のようなものです。 !\[図\](https://img.atcoder.jp/ghi/a85459a03d436560bfe2e911d8cec4e6.png)