트리의 자기동형사상 개수

트리는 임의의 두 정점이 많아야 하나의 단순 경로(정점을 중복해서 지나지 않는 경로)로만 연결되는 무향 그래프입니다.

정점이 $n$개이고 $1$번부터 $n$번까지 번호가 매겨진 트리를 생각합니다. $P$를 이 트리의 정점들에 대한 순열, 즉 일대일 대응 $P : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$라고 합시다. 임의의 두 정점 $u$, $v$에 대해 $P(u)$와 $P(v)$가 간선으로 연결되어 있다는 것과 $u$와 $v$가 간선으로 연결되어 있다는 것이 서로 필요충분조건일 때, 순열 $P$를 자기동형사상(automorphism)이라고 부릅니다.

주어진 트리의 서로 다른 자기동형사상의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 구하세요.

첫째 줄에 트리의 정점 개수 $n$ ($1 \le n \le 500{,}000$)이 주어집니다. 이어지는 $n - 1$개의 줄에는 각각 두 정수 $u_i$와 $v_i$ ($1 \le u_i < v_i \le n$)가 주어지며, 이는 정점 $u_i$와 $v_i$를 잇는 간선을 나타냅니다.

주어진 트리의 서로 다른 자기동형사상의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 한 줄에 출력하세요.

위 트리에는 $8$개의 자기동형사상이 있습니다. 그 중 세 가지는 다음과 같습니다.

• $i = 1, 2, 3, 4, 5, 6$에 대해 $p(i) = i$ (항등사상)
• $i = 1, 2, 3, 4$에 대해 $q(i) = i$이고 $q(5) = 6$, $q(6) = 5$
• $r(1) = 6$, $r(2) = 5$, $r(3) = 4$, $r(4) = 3$, $r(5) = 1$, $r(6) = 2$