Alice has received a beautiful tree as a gift from her math teacher. This tree has $N$ nodes connected by $N-1$ edges, and each node is assigned a value represented by $arr[i]$.

Alice enjoys playing with this tree by cutting certain edges and dividing it into multiple subtrees. She has a favorite number $X$, and she's curious to find out the number of ways she can cut the tree into subtrees so that the sum of values in each subtree is divisible by $X$. The cutting order of the edges doesn't matter.

Help Alice solve this interesting problem by determining the count of good cuttings she can make when dividing the initial tree into $1$ subtree, $2$ subtrees, $3$ subtrees, and so on, up to $N$ subtrees.

• A good cutting is a cutting in which sum of all values of each subtree is divisible by $X$.

As the number of good cuttings can be huge you need to print the answer modulo $10^9+7$.

 Input format

• First line of the input contains an integer $T$, representing the number of test cases.
• The first line of each test case contains $2$ integers $N$, $X$.
• The next line of each test case contains $N$ integers separated by a space, representing the array $arr$.
• The next $N-1$ lines of each test case contains $2$ integers each, representing an edge of the tree.

Output format

• For each test case, output $N$ integers separated by a space telling the count of good cuttings when dividing the tree into $1$ subtree, $2$ subtrees, $3$ subtrees, and so on, upto $N$ subtrees.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 10^5$
• $1 \leq arr[i], X \leq 10^9$
• It is guaranteed that sum of $N$ over all test cases does not exceed $2*10^5$