A k player turn based game (also known as sequential game) can be represented as a rooted tree T where each non-leaf node is colored with one of k colors. Each node in the tree represents a game state. Suppose that the current state of the game corresponds to a node u with color i. Then the player i gets to make a move. Each edge connecting node u to one of its children corresponds to a valid move at that game state. If player i gives the move corresponding to the edge (u, v) then the game state will change from u to v. The leaf nodes indicate the terminal states of the game (the game is over and no player can give a move) and thus are colorless.

A strategy for player i is just an assignment of moves for all possible game states that may arise in the game. Note that not all states can arise in a game because by assigning a move in one state we can guarantee that certain states may never arise. Similar to how a game can be represented with a rooted tree T, a strategy for player i can be represented with a (rooted) subtree of that tree T.

More formally, a strategy for a player i given a rooted tree T (where all the non-leaf nodes are colored with integers from 1 to k) is a rooted subtree T′ that satisfies the following constraints:

1. T and T′ share the same root.
2. Every non-leaf node with color i in T′ has exactly one child.
3. For every non leaf node in T′ with color not equal to i, all of its children in T are also in T′.

In this problem, you will be given a rooted tree T for such a k player game. For each player, we want to find out how many strategies the player can have.

The first line of the input will contain an integer t representing the number of test cases. Each test case is described by 3 lines. On the first line, you will be given a pair of integers n and k, the number of nodes in the tree and the number of players in the game T. On the second line, you will be given n space separated integers p₁, p₂, p₃, ..., p_n (0 ≤ p_i ≤ n) where p_i denotes the parent of the i^th node in the tree for all non-root nodes. p_i = 0 if i is the root. On the third line, you will be given n space separated integers c₁, c₂, ... , c_n (0 ≤ c_i ≤ k) where c_i denotes the color of node i for all non-leaf nodes. c_i = 0 if i is a leaf.

Constraints

• 1 ≤ k ≤ n ≤ 10⁶ and the sum of n over all test cases will not exceed 10⁶.

For each test case you will print the case number and k integers s₁, s₂, ..., s_k where s_i is the number of strategies for player i in the game T modulo 10⁹ + 7.

Explanation of Sample Input

The tree from the sample input is show bellow:

Here we show the nodes with color 1 in red, 2 in green and 3 in blue. Player 2 has 6 strategies in this game, which are:

Examples of Non-Strategies

The following figure shows three examples of subtrees that are not valid strategies of player 2: