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\)