题目描述：
王小明有一颗圣诞树，它是这样的优美以至于满足图论中树的定义。现在他要装饰它，方法很简单，即用刷子将它的节点染色，但是作为一个计算机专业的学生，他知道计算机中颜色一般有256256256种，但他不满足于此。他希望总颜色数是一个他喜欢的幸运数字，比如说19260817，正所谓颜色越多，快乐越多。 当他正在涂的时候，李丽看到了，就想了个法子希望能难倒小明，她要求小明只能选下标（树的下标从1开始）为x的倍数的节点染色，同时对于某个选择的根，所有染色点到根的路径上不出现重复的颜色。出于小明的直男审美，他竟然觉得不重复的颜色挺美的，大方采纳了该染色计划，同时他开始思考有多少种可能的染色方案恰好使用了y种颜色，两种染色方案被视为不同的当且仅当存在一个点在两种方案下颜色不同。 充满勇气敢于挑战的小明希望处理多个询问，由于他比较懒，他希望所有待涂节点总数小于1000000（1e6），最后他要求你也来写一个程序验证他的工作。
输入格式：
第一行包含一个整数n，表示树的大小； 接下来n-1行每行包含两个整数$u_i$和$v_i$，表示树的一条边($u_i$,$v_i$)； 接下来一行包含两个整数q和m，分别表示询问的个数以及总颜色数。 最后q行中，第i行包含两个整数$x_i$和$y_i$，分别表示选择所有下标为$x_i$的倍数节点染色并以$((i-1) mod \lfloor \frac{n}{x_i} \rfloor + 1) * x_i$为新的树根，恰好染了$y_i$种颜色的方案。
输出格式：
输出q行，每行一个整数表示mod 1000000007（1e9+7）意义下满足条件的染色方案数。
样例输入：
8 1 2 2 3 2 6 1 4 4 5 6 7 6 8 2 8 2 1 3 2
样例输出：
0 56
样例解释：
第一组询问显然不可能完成，故方案数为0 第二组询问涉及到的点只有两个，而且两者颜色需不同，故总共有8*7=56种方案。
数据范围：
对于20%的数据满足：n $\leq$ 10，q $\leq$ 5，m $\leq$ 4，$yi \leq$ 4 对于50%的数据满足：n $\leq$ 2000，q $\leq$ 1000，m $\leq$ 100，$y_i \leq$ 100 对于100%的数据满足：n $\leq$ 200000，q $\leq$ 100000，m $\leq$ 1000000000，$y_i \leq$ 100 另外：对于100%的数据，都有$\sum\limits_{i=1}^n\frac{n}{x_i} \leq$ 1000000，$y_i \leq$ m;
备注：
选手文件夹下存在该题大样例，满足50%数据对应规模。