Aleksei 收到一棵大細為 $n$ 嘅蘋果樹作為生日禮物。身為一名演算法競賽選手,佢決定計下棵樹上面有幾多個 $k$-蘋果批。
一棵大細為 $n$ 嘅蘋果樹定義為一棵有 $n$ 個頂點、以頂點 $1$ 為根嘅有根樹,其中每個頂點嘅直接子節點數量都嚴格少過佢父節點嘅直接子節點數量(冇父節點嘅根節點除外)。
一個 $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$-蘋果批由一個頂點 $v$(中心)同埋另外 $k - 1$ 個同 $v$ 距離相同嘅頂點組成。
你嘅任務係計算喺給定嘅樹入面有幾多個 $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\}$。