Aleksei は誕生日プレゼントとしてサイズ $n$ のリンゴの木をもらいました。競技プログラマーである彼は、その木の上にある $k$-アップルパイの個数を数えることにしました。
サイズ $n$ のリンゴの木とは、頂点 $1$ を根とする $n$ 頂点の根付き木であって、(親を持たない根を除き)各頂点の直接の子の個数がその親の直接の子の個数より真に少ないものとして定義されます。
$k$-アップルパイとは、次の条件を満たす組 $(v, S)$ です:
- $v \in V$ は木の頂点(中心)である。
- $S \subset V \setminus \{v\}$ はサイズ $k - 1$ の頂点集合である。
- ある整数 $d$ が存在して、すべての $u \in S$ に対して $\text{dist}(v, u) = d$ が成り立つ。
距離 $\text{dist}(u, v)$ は、頂点 $u$ と頂点 $v$ の間の単純パス上の辺の本数として定義されます。
言い換えると、$k$-アップルパイは 1 つの頂点 $v$(中心)と、$v$ からすべて同じ距離にある他の $k - 1$ 個の頂点からなります。
あなたの仕事は、与えられた木における $k$-アップルパイの個数を求めることです。
答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。
入力
各テストは複数のテストケースを含みます。1 行目にはテストケースの個数 $t$ ($1 \le t \le 10^4$) が与えられます。続いて各テストケースの説明が与えられます。
各テストケースの最初の行には 2 つの整数 $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 つの整数を出力してください。
入出力例
入力 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\}$ です。