给定一棵有n个结点的树 T，结点依次以1,2,……,n标号。树T的深度优先遍历序可由以下过程得到: 1.选定深度优先遍历的起点s(1≤s≤n)，当前所在结点即是起点。 2.若当前结点存在未被遍历的相邻结点u则遍历u，也即令当前所在结点为u并重复这一步;否则回溯。 3.按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序是任意的，因此对于同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对109取模之后的结果。
第一行，一个整数 n，表示树T的结点数。 接下来n-1行，每行两个正整数 ui,vi，表示树 T 中的一条连接结点 ui,vi 的边。
输出⼀⾏，⼀个整数，表⽰树T的不同的深度优先遍历序数量对109取模的结果.
4 1 2 2 3 3 4
6
8 1 2 1 3 1 4 2 5 2 6 3 7 3 8
112
