树是一个无向图，其中任意两个节点之间最多有一条简单路径，即不重复经过节点的路径。

考虑一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$。设 $P$ 为树节点集合的一个排列，即一个一一映射（单射）$P : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$。如果对于树中任意两个节点 $u$ 和 $v$，当且仅当 $u$ 和 $v$ 之间有边相连时，$P(u)$ 和 $P(v)$ 之间也有边相连，则称排列 $P$ 为该树的一个自同构。

我们希望求出给定树的不同自同构数量，结果对 $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$ 取模。

样例

输入 1

6
1 3
2 3
3 4
4 5
4 6

输出 1

8

说明

这棵树共有 8 个自同构，其中包括以下三个：

• $p(i) = i$，对于 $i = 1, 2, 3, 4, 5, 6$

• $q(i) = i$，对于 $i = 1, 2, 3, 4$，且 $q(5) = 6, q(6) = 5$

• $r(1) = 6, r(2) = 5, r(3) = 4, r(4) = 3, r(5) = 1, r(6) = 2$。