时间限制：1.0 s 内存限制：512.0 MB

题目描述

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

1. 选定深度优先遍历的起点s（1≤s≤n），当前所在结点即是起点。
2. 若当前结点存在未被遍历的相邻结点u则遍历，也即令当前所在结点为u并重复这一步；否则回溯。
3. 按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。

由于起点的选择是任意的，且相邻结点的遍历顺序是任意的，同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序，结果对10^9取模。

输入格式

第一行一个整数n，表示树T的结点数。 接下来n-1行，每行两个正整数u_i, v_i，表示树T中连接结点u_i和v_i的边。

输出格式

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

样例

样例1

输入：

4
1 2
2 3
3 4

输出：

6

样例2

输入：

8
1 2
1 3
1 4
2 5
2 6
3 7
3 8

输出：

112

数据范围

• 对于40%的测试点，保证1≤n≤8
• 对于另外20%的测试点，保证给定的树是一条链
• 对于所有测试点，保证1≤n≤10^5