Aleksei는 생일 선물로 크기가 $n$인 사과나무를 받았습니다. 경쟁적 프로그래머인 그는 나무에서 만들 수 있는 $k$-사과파이의 개수를 계산해 보기로 했습니다.
크기가 $n$인 사과나무는 정점 $1$을 루트로 하고 $n$개의 정점을 가지는 루트 있는 트리로 정의되며, 여기서 (부모가 없는 루트를 제외한) 각 정점은 자신의 부모보다 직접적인 자식 정점의 수가 엄격히 적습니다.
$k$-사과파이는 다음 조건을 만족하는 쌍 $(v, S)$입니다:
- $v \in V$는 트리의 한 정점(중심)입니다.
- $S \subset V \setminus \{v\}$는 크기가 $k - 1$인 정점들의 집합입니다.
- 모든 $u \in S$에 대해 $\text{dist}(v, u) = d$를 만족하는 정수 $d$가 존재합니다.
거리 $\text{dist}(u, v)$는 정점 $u$와 $v$ 사이의 단순 경로에 있는 간선의 개수로 정의됩니다.
즉, $k$-사과파이는 하나의 정점 $v$(중심)와 $v$로부터의 거리가 모두 같은 다른 $k - 1$개의 정점으로 이루어집니다.
당신의 과제는 주어진 트리에서 $k$-사과파이의 개수를 구하는 것입니다.
답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하십시오.
입력
각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.
각 테스트 케이스는 사과나무의 정점 개수와 사과파이의 크기를 나타내는 두 정수 $n$과 $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$)가 포함된 줄로 시작합니다.
다음 줄에는 $n - 1$개의 정수 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)이 주어지며, 여기서 $p_i$는 사과나무에서 정점 $i$의 부모를 나타냅니다.
모든 테스트 케이스에 걸친 $n$의 합은 $5 \cdot 10^5$을 초과하지 않습니다.
출력
각 테스트 케이스마다 $k$-사과파이의 개수를 $998\,244\,353$으로 나눈 나머지를 나타내는 정수 하나를 출력합니다.
예제
입력 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
출력 1
1 20 16
참고
첫 번째 테스트 케이스에서 유일하게 존재하는 파이는 정점 $1$을 중심으로 하며, 이에 대응하는 집합은 $S = \{2, 3\}$입니다.