It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
As is known, Guangtou Qiang earns his living by cutting trees. One day he found a giant tree in a big forest jungle in No.1037, LuoYu Rd. As he has no car for transportation, he decides to cooperate with the evil Wood Hurting Union(WHU), which possesses several types of motorcycles. Each motorcycle can transport a tree whose weight is no larger than wi. Since the value may be less than the total weight of this tree, he will cut some branches of the tree to satisfy the limits. Still, Mr. Qiang wants to earn as much as possible, he wishes to keep the weight of the cut tree to exactly wi. Now Mr. Guang wants to pick up one motorcycle. Can you tell him for each motorcycle how many ways he can to cut a tree satisfying all the requirements?
For simplicity, you may assume this tree to be an unrooted weighted tree in Graph Theory. Each node has a value vi and the total weight of the tree is ∑vi . You can delete some vertices and all edges linked to it, but the remaining graph should still be connected.
The first line consists of an integer n(1≤n≤3000), denoting the size of the tree.
Next line contains n integers vi (0≤vi≤2000), denoting the weight of i-th node.
The next n-1 lines contain two integers u and v, representing an edge connecting node u and node v. Nodes are numbered from 1 to n. It is guaranteed that the resulting graph is a connected tree.
Next line is a integer q(1≤q≤10), the number of Mr Qiang's motorcycles.
The next q lines contain only an integer wi (0≤wi≤2000). Each represents the admitted weight of Mr. Qiang's i-th motorcycle.
For each of WHU's motorcycle, you should output the number of ways to cut a tree to its admitted weight. Since the answer may be very large, you need to output the answer modulo 998244353. (998244353 is a prime number)