Aruba i Ball znów grają w grę; będziemy ich nazywać odpowiednio A i B.

Dana jest drzewo ukorzenione o $n$ wierzchołkach, ponumerowanych od $1$ do $n$, gdzie korzeniem jest wierzchołek $1$. Każdy wierzchołek ma albo $0$, albo $2$ synów. Dzielimy wierzchołki na trzy kategorie:

• ${A}$: zbiór wszystkich wierzchołków wewnętrznych, których odległość od korzenia jest parzysta (odległość korzenia od samego siebie wynosi $0$).
• ${B}$: zbiór wszystkich wierzchołków wewnętrznych, których odległość od korzenia jest nieparzysta.
• ${L}$: zbiór wszystkich liści.

Każdemu liściowi $u\in{L}$ przypisana jest para $(c(u), d(u))$, gdzie $c$ i $d$ można traktować jako funkcje o dziedzinie ${L}$.

Przed rozpoczęciem gry:

• A dla każdego wierzchołka $u\in{A}$ wybiera jedną z dwóch krawędzi prowadzących do synów i oznacza ją jako krawędź ciężką.
• B dla każdego wierzchołka $u\in{B}$ wybiera jedną z dwóch krawędzi prowadzących do synów i oznacza ją jako krawędź ciężką.

Wybór A można traktować jako funkcję $f$ o dziedzinie ${A}$, a wybór B jako funkcję $g$ o dziedzinie ${B}$.

Para $(f,g)$ nazywana jest strategią. A ma $2^{|{A}|}$ możliwych wyborów, a B ma $2^{|{B}|}$ możliwych wyborów. Łącznie istnieje $2^{|{A}|+|{B}|}$ różnych strategii.

Po ustaleniu strategii, gra rozpoczyna się w korzeniu i przebiega wzdłuż krawędzi ciężkich aż do osiągnięcia liścia $u$. Wtedy wynik A wynosi $c(u)$, a wynik B wynosi $d(u)$. Strategia $(f, g)$ jest punktem równowagi Nasha, jeśli spełnione są następujące warunki:

• Przy ustalonym wyborze A, gracz B nie może uzyskać wyższego wyniku poprzez zmianę swojej strategii. Oznacza to, że dla każdej strategii $(f, g')$, wynik B jest mniejszy lub równy wynikowi B w strategii $(f, g)$.
• Przy ustalonym wyborze B, gracz A nie może uzyskać wyższego wyniku poprzez zmianę swojej strategii. Oznacza to, że dla każdej strategii $(f', g)$, wynik A jest mniejszy lub równy wynikowi A w strategii $(f, g)$.

Dla danej struktury drzewa i liczby $k$, gdzie wartości $c$ i $d$ należą do zbioru ${Z}\cap[1,k]$, istnieje $k^{2|{L}|}$ różnych par $(c,d)$. Należy obliczyć liczbę punktów równowagi Nasha dla każdej z tych par. Ponieważ $k^{2|{L}|}$ jest bardzo duże, należy obliczyć sumę tych wartości modulo $p$. Innymi słowy, oblicz:

$$\left(\sum_{c\in{{L}\to[k]}}\sum_{d\in{{L}\to[k]}}F(c,d)\right)\bmod p$$

gdzie ${L}\to[k]$ to zbiór wszystkich funkcji o dziedzinie ${L}$ i wartościach w $[k]=\{1,2,\dots,k\}$, a $F(c, d)$ to liczba punktów równowagi Nasha dla danych $c$ i $d$.

A i B uważają, że drzewo jest zbyt duże i chcą rozważyć każde poddrzewo. Dla każdego wierzchołka $s$, usuwamy resztę drzewa, pozostawiając jedynie poddrzewo zakorzenione w $s$, i rozpoczynamy grę z $s$ jako korzeniem. Wynik dla tak zdefiniowanego problemu oznaczamy jako $Ans_s$.

Należy obliczyć $Ans_s\bmod p$ dla każdego wierzchołka $s$.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $n, k, p$ ($3\leq n\leq 5000, k\le 10^9, n< p\leq 10^6$). Gwarantuje się, że $n$ jest liczbą nieparzystą.

Druga linia zawiera $n-1$ liczb całkowitych $fa_2, fa_3, \dots, fa_n$, gdzie $fa_i$ oznacza ojca wierzchołka $i$, przy czym $1\leq fa_i < i$.

Wyjście

Wypisz $n$ linii, w każdej z nich jedną liczbę: $Ans_i\bmod p$ dla $i$-tego wierzchołka.

Przykład

Przykład 1

Wejście:

3 2 114514
1 1

Wyjście:

24
4
4

Przykład 2

Wejście:

9 2 191981
1 1 3 4 4 3 7 7

Wyjście:

8960
4
1152
24
4
4
24
4
4

Przykład 3

Wejście:

11 45 233
1 1 3 3 5 5 4 4 9 9

Wyjście:

80
161
177
150
80
161
161
161
80
161
161

Podzadania

• Podzadanie $1(20\,\mathrm{pkt})$: $n=99, k\leq 100$, $p$ jest liczbą pierwszą.
• Podzadanie $2(30\,\mathrm{pkt})$: $n=99$.
• Podzadanie $3(50\,\mathrm{pkt})$: $n=4999$.