单点时限: 6.0 sec
内存限制: 1024 MB
Mr Frog likes traveling, and once he came to a magical country. The country has $n$ cities, connected with $n-1$ bi-directional roads. Each city was assigned a level of beauty $b$ by Mr Frog. Mr Frog had planned several travels in the country. For each plan, there was a fixed departure city $s$ and a fixed destination city $t$. He could choose several cities to explore in detail, but he would only choose the cities on the shortest path from $s$ to $t$ (including $s$ and $t$). He favored the number $k$, so he wanted to choose some cities so that the sum of the level of beauty of those cities can be divided by $k$.
Mr Frog asked you for helping him calculate the number of different choices satisfying his requirement. Two choices are different if Mr Frog would visit one city in one choice but would not visit that city in another choice. For sake of convenience, just output the answer modulo $998244353$.
The first line contains two integers $n$ and $k$ ($1 \leq n \leq 2 \times 10^5, 2 \leq k \leq 50$).
Each of the next $n-1$ lines contains two integers $x$ and $y$ ($1 \leq x, y \leq n)$, indicating there is a road connecting the city $x$ and $y$.
The next line contains $n$ integers $b_1, \dots, b_n$ ($0 \leq b_1, \dots, b_n < k$), where $b_i$ represents the level of beauty of city $i$.
The next line contains an integer $q$ ($1 \leq q \leq 10^6$), indicating the number of travel plans.
Each of the next $q$ lines contains two integer $s$ and $t$ ($1 \leq s, t \leq n$).
For each plan, print on a line the number of different choices modulo $998244353$.
5 2 1 2 2 3 3 4 4 5 1 0 1 0 1 3 1 3 2 4 1 5
4 4 16