5849 - GESP:2025-6月等级8-T2-遍历计数

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

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

第一步中起点的选择是任意的，并且第二步中遍历相邻节点的顺序是任意的

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

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

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