Number of Tree Automorphisms

A tree is an undirected graph in which any two nodes are connected by at most one simple path (a path that does not repeat nodes).

Consider a tree with $n$ nodes numbered from $1$ to $n$. Let $P$ be a permutation of the tree's nodes, that is, a bijection $P : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$. The permutation $P$ is an automorphism if, for every pair of nodes $u$ and $v$, the nodes $P(u)$ and $P(v)$ are joined by an edge if and only if $u$ and $v$ are joined by an edge.

Count the number of distinct automorphisms of a given tree, modulo $1{,}000{,}000{,}007$.

The first line contains an integer $n$ ($1 \le n \le 500{,}000$), the number of nodes in the tree. Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i < v_i \le n$) describing an edge between nodes $u_i$ and $v_i$.

Print a single integer: the number of distinct automorphisms of the given tree, taken modulo $1{,}000{,}000{,}007$.

The tree above has $8$ automorphisms. Three of them are:

• $p(i) = i$ for $i = 1, 2, 3, 4, 5, 6$ (the identity)
• $q(i) = i$ for $i = 1, 2, 3, 4$, with $q(5) = 6$ and $q(6) = 5$
• $r(1) = 6$, $r(2) = 5$, $r(3) = 4$, $r(4) = 3$, $r(5) = 1$, $r(6) = 2$