题号：NC19154
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
wyf非常喜欢旅行，现在他来到了一个神奇的国家，这个国家有n个城市，城市之间通过n-1条双向道路相连，且任意两个城市通过唯一的简单路径互相到达。wyf已经为自己在这个国家规划了一些旅行，每次旅行他都会选择一个出发的城市S和到达的城市T。在此之前他为这个国家的每一座城市都评估了一个美丽值，而在从S旅行到T的期间，他可以选择一些城市认真游览一番（当然他不会绕路游览某个城市）。他的幸运数字是K，而他希望自己能够一直幸运下去，所以他希望自己一次旅行所停留游览的城市的美丽值之和是K的整数倍。对于每一次你能不能告诉他他有多少种游览的方案
输入描述:
两个正整数N，K表示城市的个数和幸运数字（1<=N<=200000 2<=K<=50）
接下来N-1行，每行两个正整数x,y表示城市x和y之间存在一条道路
接下来一行n个正整数，第i个正整数表示城市i的美丽值
一个正整数q表示旅行的次数（1<=q<=200000）
接下来q行，每行两个正整数S,T表示一次旅行的起点和终点（1<=S,T<=N）
输出描述:
对于每一次旅行，一行正整数表示游览的方案数
答案对998244353取模。
示例1
输入
复制
5 2
1 2
2 3
3 4
4 5
1 0 1 0 1
3
1 3
2 4
1 5