쿠냐브스키 파벨

Carol과 David가 게임을 한다. 루트가 있는 이진 트리(각 정점의 자식이 0개 또는 2개)와 정수 $k$가 주어진다. 정점의 깊이는 루트로부터의 거리이다. 각 리프에는 정수 순서쌍이 하나씩 들어 있다. 순서쌍의 원소는 $0$ 이상 $k - 1$ 이하이다.

$E$를 높이가 짝수인 내부(리프가 아닌) 정점의 집합, $O$를 높이가 홀수인 내부 정점의 집합이라 하자. $E$의 각 정점에서 Carol은 자식 중 하나를 표시한다. 표시할 정점의 집합이 Carol의 전략이다. Carol이 가질 수 있는 전략은 $2^{|E|}$가지이다. David도 $O$의 정점에 대해 같은 일을 한다. 따라서 그가 가질 수 있는 전략은 $2^{|O|}$가지이다. 이 문제에서는 순수 전략만 고려한다.

토큰을 루트에 놓고, 리프에 도착할 때까지 표시된 자식으로 계속 이동시킨다. 이 리프에 들어 있는 정수 순서쌍을 $(c, d)$라 하자. Carol은 $c$를, David는 $d$를 보상으로 받는다.

상대방의 전략이 그대로일 때 어느 플레이어도 자신의 전략을 바꿔 더 좋은 보상을 받을 수 없다면, 그 두 전략의 쌍은 내시 균형을 이룬다.

트리는 주어지지만 리프에 들어 있는 정수 순서쌍은 주어지지 않는다. 리프에 순서쌍을 넣는 방법은 $k^{2L}$가지이며, 여기서 $L$은 리프의 개수이다. 리프에 순서쌍을 넣는 모든 방법에 대해 내시 균형을 이루는 전략 쌍의 개수의 합을 구하라.

정답은 998244353으로 나눈 나머지를 출력하라. 형식적으로, 실제 답이 $y$이고 출력한 답이 $x$일 때 $-2^{63} \leq x < 2^{63}$이고 $x-y$가 998244353으로 나누어떨어지면 정답으로 인정된다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다($3 \leq n < 5000$, $1 \leq k \leq 20$). $n$은 트리의 정점 개수, $k$는 리프에 들어 있는 순서쌍 원소의 상한이다.

둘째 줄에 $n - 1$개의 정수 $p_i$가 주어진다($0 \leq p_i < i$). 이 중 $i$번째(1부터 센다)는 정점 $p_i$와 $i$를 잇는 간선을 나타낸다. 각 정수는 $p_i$ 안에서 0번 또는 2번 나타난다.

정답을 998244353으로 나눈 나머지를 한 줄에 출력한다.

리프에 순서쌍을 넣는 방법은 $3^4$가지, Carol의 전략은 $2$가지, David의 전략은 $1$가지이다(David는 아무것도 고를 수 없으므로 이 전략은 다소 퇴화되어 있다). 리프에서 Carol이 받는 보상이 모두 같으면 Carol의 두 전략이 David의 유일한 전략과 내시 균형을 이루고, 그렇지 않으면 보상이 더 큰 리프를 표시하는 전략만 그렇게 된다. Carol의 보상이 같은 배정이 $3 \cdot 3^2$가지, 다른 배정이 $6 \cdot 3^2$가지이다. 답은 $27 \cdot 2 + 54 = 108$이다.