时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
众所周知，动态树中有一个经典的操作叫Access（别紧张，做这题不需要会动态树），在一棵有根树中，边有两种：虚边和实边，一个点最多和一个儿子之间有实边（我们称之为实儿子边）。
当我们执行 Access(x) 时，首先会把
到根这条路径上的所有点的实儿子边全变成虚边，然后把这条路径上的所有边全变成实边。
现在给定一棵
个点的有根树（根的编号为 
），一开始所有边都是虚边，你可以进行最多 
次任意的 
操作，求树有几种可能的形态？
两个形态不同，当且仅当存在某条边，在一个形态里是虚边，另一个里是实边。
由于答案可能很大，你只需要输出答案对
取模后的值。
当我们执行 Access(x) 时，首先会把
现在给定一棵
两个形态不同，当且仅当存在某条边，在一个形态里是虚边，另一个里是实边。
由于答案可能很大，你只需要输出答案对
输入描述:
第一行两个整数
接下来行，每行两个数
，表示有一条边
，注意我们虽然是个根为
输出描述:
输出答案对