AND on a Tree Again#13124

AND on a Tree Again

5 seconds
256 megabytes

Let denote the number of set bits in the binary representation of a non-negative integer .

You are given a tree with vertices and an integer . For each vertex , consider the following problem.

Vertex is the root of the tree. It is assigned the number 2^m-1, while every other vertex is assigned an integer from to 2^m-1, inclusive. Let be the bitwise AND of the numbers on the path from the root to vertex , including both endpoints.

An assignment is attractive if \operatorname{popcount}(\operatorname{AND}(v)) is the same for all non-root vertices . Find the number of attractive assignments for every possible root, modulo .

If n=1, the only assignment is considered attractive.

Input

The first line contains an integer (1\le t\le10^4) — the number of test cases.

The first line of each test case contains two integers and (1\le n,m\le10^5).

Each of the next n-1 lines contains two integers and (1\le u,v\le n) — the endpoints of an edge. The given edges are guaranteed to form a tree.

The sum of over all test cases does not exceed 10^5. The sum of does not exceed 10^5 either.

Output

For each test case, print one line containing integers. The -th integer must be the number of attractive assignments rooted at vertex , modulo .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first test case of the first example, the tree has one vertex, so the answer is .

In the second test case of the first example, the root is assigned the number . The other vertex can be assigned any of , , or , so the answer is for either root.

Scoring

  1. Subtask ( points): t\le10, n,m\le5.

  2. Subtask ( points): n,m\le20.

  3. Subtask ( points): the degree of every vertex is at most .

  4. Subtask ( points): the tree is a star, meaning that a vertex is adjacent to every other vertex.

  5. Subtask ( points): n,m\le1000, \sum n\le5000, \sum m\le5000.

  6. Subtask ( points): no additional constraints.