时间限制：2500 ms
内存限制：768 MiB
标准输入输出
题目类型：传统
评测方式：无测试数据
黑猫的世界正在走向终结。
在这个正在走向终结的世界里，Liki 和 Sasami 需要找到世界的真相。具体来说，这个世界可以看做一棵 个结点的有根树，根结点的编号为 。并且存在一种对树进行深度优先搜索的方案，使第 次访问的结点为 。也就是说 可以构成这棵树的一个 dfs 序。在最开始，所有的结点都没有崩溃。
每一天，Liki 和 Sasami 会探索一个没有崩坏的结点 。在这次探索后，为了引导他们发现世界真相，黑猫会使 及子树中所有点崩坏。
同时，在第 天 Liki 和 Sasami 的探索结束后，由于自身力量枯竭，第 号结点若没有崩坏，则会崩坏。
分别对 求 Liki 和 Sasami 有多少种恰好探索 天的探索方案，满足最后一次探索的是 号结点，对 取模。
第一行一个数，，代表树的结点数 。
接下来 行每行两个数 ，代表结点 和结点 之间有一条边。
输出 个数，第 个数代表探索 天的方案数，对 取模。
样例输入 1
样例输出 1
样例输入 2
复制7
4 2
6 1
5 1
7 6
2 3
1 2
样例输出 2
样例 #1 解释
对于样例 ，以下 种探索序列合法：
。
来源与致谢
来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。
数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。