------ 致所有退役 ACMer

众所周知，小帅是一个退役二次元 ACMer，他经常 yy 自己进入二次元的世界。

有一天，小帅在梦乡中进入了自己幻想的二次元世界，作为一个佛系的种田玩家，小帅最喜欢种田，于是，他决定种一颗希望之树，希望之树由若干个节点组成，每个节点第二天会生成两个额外的子节点，初始节点数为 (第 天)，根节点编号为 ，当然勤劳的小帅很快被二次元的妹子注意到了，妹子对希望之树非常感兴趣，答应如果小帅 内回答出她的所有问题，就成为他的女朋友。

单身的小帅非常希望可爱的二次元妹子成为自己女友，由于小帅在梦里，他拿不到自己的电脑，无法回答妹子的问题，所以他请教了聪明的你，如果你帮他回答出了妹子的所有问题，小帅将把你的出题数 。

妹子一共有 个问题，每次询问，会给你两个整数 和 ，表示询问第 天深度为 的节点的数量，由于答案可能很大，你只需要输出答案对 取模后的结果。

第一行输入两个整数 。

接下来  行，每行两个整数 ，表示  和  之间有一条边。

接下来  行，每行两个正整数 。

保证输入构成一颗树。

对于每次询问，输出一个整数，表示答案对  取模后的结果。

2 2
1 2
2 2
3 3

5
18