Khalin 그래프

리틀 조지 칼린(Little George Khalin)은 새로운 종류의 그래프를 설계했다. 그는 알파벳 K를 싫어해서 그 글자를 버렸다.

트리의 전위 순회 순서(preorder) (time-in order라고도 부른다)는 다음 절차로 얻는다.

트리의 루트를 하나 정하고, 모든 간선을 루트에서 멀어지는 방향으로 향하게 한다. 정점 $v$의 부분트리의 전위 순회 순서는 $v$ 다음에 $v$의 모든 자식 부분트리의 전위 순회 순서를 어떤 순서로든 이어 붙인 것이다(자식이 없으면 $v$만 있다). 루트가 고정된 트리의 전위 순회 순서란 루트 부분트리의 임의의 전위 순회 순서를 말한다.

같은 트리라도 전위 순회 순서는 여러 개일 수 있다. 전위 순회 순서는 루트를 어떻게 고르는지, 그리고 각 정점에서 자식 부분트리를 어떤 순서로 보는지에 따라 달라지기 때문이다.

Halin 그래프는 다음 절차로 얻는다. 기저 트리라고 부르는 트리가 있는데, 이 트리는 정점이 4개 이상이고 차수가 2인 정점이 없다. 이 트리의 전위 순회 순서 하나가 주어진다. 이 순서에 대해 트리의 루트는 잎이 아니다.

트리의 잎을 전위 순회 순서에 나타나는 순서대로 $v_1, v_2, \ldots, v_m$이라 하자. $i$가 $1$부터 $m$까지 각각에 대해 $v_i$와 $v_{(i \bmod m) + 1}$을 잇는 간선을 트리에 추가한다. 이 간선들을 추가 간선이라 한다. 결과로 얻은 그래프가 기저 트리와 주어진 전위 순회 순서에 대한 Halin 그래프이다.

그래프 $G$의 3-매칭은 간선들의 집합 $S$ 중에서, $G$에서 $S$에 속하지 않은 간선을 모두 제거했을 때 생기는 연결 요소가 크기 3 또는 1인 트리인 것이다.

주어진 Halin 그래프의 3-매칭 개수를 $998\,244\,353$으로 나눈 나머지를 구하라.

첫째 줄에 기저 트리의 정점 개수 $n$ ($4 \leq n \leq 10^5$)이 주어진다. 정점은 전위 순회 순서에 따라 번호가 매겨져 있다.

둘째 줄에는 정수 $n-1$개가 주어진다. $i$번째 정수는 $p_i$ ($1 \leq p_i \leq i$)이며, 기저 트리에서 $p_i$번 정점과 $i+1$번 정점 사이의 간선을 나타낸다.

기저 트리가 트리이고, 차수가 2인 정점이 없으며, 정점 $1$이 잎이 아님이 보장된다.

주어진 그래프의 3-매칭 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력하라.

첫 번째 예제에서 실제 Halin 그래프는 정점 4개의 완전 그래프이다.

두 번째 예제에서 잎은 $[2, 4, 5, 6]$이므로 추가 간선은 4개이다. 즉 $(2, 4)$, $(4, 5)$, $(5, 6)$, $(6, 2)$이다.

문제 설명의 의미 있는 부분에는 알파벳 K가 없다는 점에 유의하라.