Aleksei otrzymał w prezencie urodzinowym jabłoń o rozmiarze $n$. Jako programista startujący w zawodach postanowił obliczyć liczbę $k$-jabłeczników na tym drzewie.
Jabłoń o rozmiarze $n$ definiujemy jako drzewo ukorzenione o $n$ wierzchołkach, z korzeniem w wierzchołku $1$, w którym każdy wierzchołek ma ściśle mniej bezpośrednich synów niż jego ojciec (z wyjątkiem korzenia, który nie ma ojca).
$k$-jabłecznik to para $(v, S)$, gdzie:
- $v \in V$ jest wierzchołkiem drzewa (środkiem),
- $S \subset V \setminus \{v\}$ jest zbiorem wierzchołków o rozmiarze $k - 1$,
- istnieje taka liczba całkowita $d$, że dla każdego $u \in S$ zachodzi $\text{dist}(v, u) = d$.
Odległość $\text{dist}(u, v)$ jest zdefiniowana jako liczba krawędzi na ścieżce prostej między wierzchołkami $u$ i $v$.
Innymi słowy, $k$-jabłecznik składa się z jednego wierzchołka $v$ (środka) oraz $k - 1$ innych wierzchołków, które znajdują się w tej samej odległości od $v$.
Twoim zadaniem jest obliczenie liczby $k$-jabłeczników w danym drzewie.
Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.
Wejście
Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^4$). Następnie podane są opisy kolejnych przypadków testowych.
Każdy przypadek testowy zaczyna się od wiersza zawierającego dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): liczbę wierzchołków jabłoni oraz rozmiar jabłecznika.
Kolejny wiersz zawiera $n - 1$ liczb całkowitych $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), gdzie $p_i$ oznacza ojca wierzchołka $i$ w jabłoni.
Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: liczbę $k$-jabłeczników modulo $998\,244\,353$.
Przykład
Wejście 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Wyjście 1
1 20 16
Uwagi
W pierwszym przypadku testowym jedyny istniejący jabłecznik ma środek w wierzchołku $1$, a odpowiadający mu zbiór to $S = \{2, 3\}$.