Aruba и Ball снова играют в игру, далее будем называть их A и B соответственно.

Дано корневое дерево с $n$ вершинами, пронумерованными от $1$ до $n$, корень имеет номер $1$. У каждой вершины либо $0$, либо $2$ сына. Разделим вершины на следующие три категории:

• ${A}$: множество всех нелистовых вершин, расстояние от которых до корня четно (расстояние от корня до самого себя равно $0$).
• ${B}$: множество всех нелистовых вершин, расстояние от которых до корня нечетно.
• ${L}$: множество всех листовых вершин.

Каждому листу $u\in{L}$ присваивается пара $(c(u), d(u))$, где $c$ и $d$ можно рассматривать как функции, определенные на ${L}$.

Перед началом игры:

• Игрок A для каждой вершины $u\in{A}$ выбирает одно из двух ребер, ведущих к сыновьям, и помечает его как «тяжелое».
• Игрок B для каждой вершины $u\in{B}$ выбирает одно из двух ребер, ведущих к сыновьям, и помечает его как «тяжелое».

Выбор игрока A можно представить как функцию $f$, определенную на ${A}$, а выбор игрока B — как функцию $g$, определенную на ${B}$.

Упорядоченная пара $(f,g)$ называется стратегией. Очевидно, что у A есть $2^{|{A}|}$ различных вариантов выбора, а у B — $2^{|{B}|}$ вариантов. Таким образом, всего существует $2^{|{A}|+|{B}|}$ различных стратегий.

После выбора стратегии игра начинается в корне дерева и продолжается вдоль тяжелых ребер до тех пор, пока не будет достигнут какой-либо лист $u$. В этот момент игрок A получает $c(u)$ очков, а игрок B — $d(u)$ очков. Стратегия $(f, g)$ является равновесием Нэша, если выполняются следующие условия:

• При фиксированной стратегии A, игрок B не может получить больше очков, изменив свою стратегию. То есть для любой стратегии $(f, g')$ выполняется $d(f, g') \leq d(f, g)$.
• При фиксированной стратегии B, игрок A не может получить больше очков, изменив свою стратегию. То есть для любой стратегии $(f', g)$ выполняется $c(f', g) \leq c(f, g)$.

Даны структура дерева и число $k$. Пусть область значений функций $c$ и $d$ — это ${Z}\cap[1,k]$. Тогда существует $k^{2|{L}|}$ различных пар $(c,d)$. Требуется вычислить количество равновесий Нэша для каждой пары $(c, d)$ и найти сумму этих количеств по всем возможным парам $(c, d)$. Поскольку это число может быть очень большим, выведите результат по модулю $p$. То есть вычислите:

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

где ${L}\to[k]$ — множество всех функций, определенных на ${L}$ со значениями в $[k]=\{1,2,\dots,k\}$, а $F(c, d)$ — количество равновесий Нэша при заданных $c$ и $d$.

A и B считают, что дерево слишком большое, и хотят рассмотреть только его поддеревья. Конкретно, для каждой вершины $s$ удалим все части дерева, кроме поддерева с корнем в $s$, и проведем игру в этом поддереве. Обозначим ответ для такой задачи как $Ans_s$.

Вам необходимо вычислить $Ans_s\bmod p$ для всех $s$ от $1$ до $n$.

Входные данные

Первая строка содержит три целых числа $n, k, p$ ($3\leq n\leq 5000, k\le 10^9, n< p\leq 10^6$). Гарантируется, что $n$ нечетно.

Вторая строка содержит $n-1$ целое число $fa_2, fa_3, \dots, fa_n$, где $fa_i$ — родитель вершины $i$, при этом $1\leq fa_i < i$.

Выходные данные

Выведите $n$ строк, в каждой строке по одному числу. В $i$-й строке выведите $Ans_i\bmod p$.

Примеры

Пример 1

Входные данные

3 2 114514
1 1

Выходные данные

24
4
4

Пример 2

Входные данные

9 2 191981
1 1 3 4 4 3 7 7

Выходные данные

8960
4
1152
24
4
4
24
4
4

Пример 3

Входные данные

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

Выходные данные

80
161
177
150
80
161
161
161
80
161
161

Подзадачи

• Подзадача $1(20\,\mathrm{баллов})$: $n=99, k\leq 100$, $p$ — простое число.
• Подзадача $2(30\,\mathrm{баллов})$: $n=99$.
• Подзадача $3(50\,\mathrm{баллов})$: $n=4999$.