遍历计数

题目描述

给定一棵有 \(n\) 个结点的树 \(T\)，结点依次以 \(1, 2, \ldots, n\) 标号。树 \(T\) 的深度优先遍历序可由以下过程得到：

1. 选定深度优先遍历的起点（\(1 \le \text{起点} \le n\)），当前所在结点即是起点。
2. 若当前结点存在未被遍历的相邻结点，则遍历该结点；否则回溯。
3. 按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。

起点选择是任意的，且遍历相邻结点的顺序是任意的，因此对于同一棵树 \(T\) 可能有多组不同的深度优先遍历序。请你求出树 \(T\) 有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对 \(10^9\) 取模之后的结果。

输入格式

第一行，一个整数 \(n\)，表示树 \(T\) 的结点数。

接下来 \(n-1\) 行，每行两个正整数 \(u, v\)，表示树 \(T\) 中的一条连接结点 \(u, v\) 的边。

输出格式

输出一行，一个整数，表示树 \(T\) 的不同的深度优先遍历序数量对 \(10^9\) 取模的结果。

样例

输入样例 1

4
1 2
2 3
3 4

输出样例 1

6

数据范围

对于所有测试点，保证 \(1 \le n \le 10^5\)。（数据范围由题面字体缺字重建，取保守范围；模数取 \(10^9\)）