After working as a junior problemsetter AUCPL.inc for a while, you start to wonder when your next promotion will be. You decide to take a look at the corporate hierarchy, to figure out the relationships each of the employees have with their subordinates.

AUCPL.inc has ~n~ employees, numbered from ~1~ to ~n~. The company hierarchy forms a rooted tree. Every employee has exactly one direct manager, except for the CEO (employee ~1~), who has no manager and is the root of the tree.

For some employee ~a~, the 'chain of managers' of ~a~ is the unique path obtained by repeatedly following the manager relationship from ~a~ up to the CEO.

The 'common manager' of a group of ~k~ employees ~a_1, a_2 \dots a_k~ is the deepest employee that lies on every path from each employee to the CEO. In other words, it is their lowest common ancestor.

For each employee ~x~, determine how many groups of ~k~ distinct employees have ~x~ as their common manager.

Input

The first line of the input contains two integers ~n\ k~ ~(1 \leq n, k \leq 10^5)~, the number of employees in AUCPL.inc, and the size of the groups we are looking for.

The next line contains ~n-1~ integers ~m_2 \dots m_n~, where ~m_i~ is the direct manager of employee ~i~ (~1 \leq m_i \leq n~). Remember that employee ~1~ is the CEO, and does not have any manager.

Output

Output ~n~ integers ~c_1, c_2, \dots, c_n~, where ~c_x~ is the number of ways to choose a group of ~k~ distinct employees whose common manager is ~x~. Since these counts may be very large, output them modulo ~10^9 + 7~.

Example

Input 1

6 2
1 1 2 2 3

Output 1

11 3 1 0 0 0

There are ~11~ groups of ~k = 2~ employees that have employee ~1~ as their common manager: ~(1,3)~, ~(1,6)~, ~(1,2)~, ~(2,3)~, ~(2,6)~, ~(1,4)~, ~(3,4)~, ~(4,6)~, ~(1,5)~, ~(3,5)~ and ~(5,6)~.

There are ~3~ groups of ~k = 2~ employees that have employee ~2~ as their common manager: ~(2,4)~, ~(2,5)~ and ~(4,5)~.

There is ~1~ group of ~k = 2~ employees that have employee ~3~ as their common manager: ~(3,6)~.

Input 3

4 3
1 1 1 1

Output 3

4 0 0 0

There are ~4~ groups of ~k = 3~ employees that have employee ~1~ as their common manager: ~(1,2,3)~, ~(1,2,4)~, ~(1,3,4)~ and ~(2,3,4)~.