Universal Cup Judging System

Universal Cup

حد الوقت: 8.0 s حد الذاكرة: 256 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Aleksei ha ricevuto un melo di dimensione $n$ come regalo di compleanno. Essendo lui stesso un programmatore competitivo, ha deciso di calcolare il numero di torte di $k$ mele presenti sull'albero.

Un melo di dimensione $n$ è definito come un albero radicato con $n$ vertici, con radice nel vertice $1$, in cui ogni vertice ha strettamente meno figli diretti rispetto a suo padre (eccetto la radice, che non ha alcun padre).

Una torta di $k$ mele è una coppia $(v, S)$ dove:

  • $v \in V$ è un vertice dell'albero (il centro),
  • $S \subset V \setminus \{v\}$ è un insieme di vertici di dimensione $k - 1$,
  • esiste un intero $d$ tale che per ogni $u \in S$ vale $\text{dist}(v, u) = d$.

La distanza $\text{dist}(u, v)$ è definita come il numero di archi sul cammino semplice tra i vertici $u$ e $v$.

In altre parole, una torta di $k$ mele è formata da un vertice $v$ (il centro) e da altri $k - 1$ vertici che si trovano tutti alla stessa distanza da $v$.

Il tuo compito è calcolare il numero di torte di $k$ mele nell'albero dato.

Poiché la risposta può essere molto grande, stampala modulo $998\,244\,353$.

Input

Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test $t$ ($1 \le t \le 10^4$). Segue la descrizione dei casi di test.

Ogni caso di test inizia con una riga contenente due interi $n$ e $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): il numero di vertici nel melo e la dimensione della torta di mele.

La riga successiva contiene $n - 1$ interi $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), dove $p_i$ indica il padre del vertice $i$ nel melo.

La somma di $n$ su tutti i casi di test non supera $5 \cdot 10^5$.

Output

Per ogni caso di test, stampa un singolo intero: il numero di torte di $k$ mele modulo $998\,244\,353$.

Esempi

Input 1

3
3 3
1 1
5 2
1 1 2 3
6 3
1 1 1 2 2

Output 1

1
20
16

Note

Nel primo caso di test, l'unica torta esistente è centrata nel vertice $1$ e l'insieme corrispondente è $S = \{2, 3\}$.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#2360EditorialOpenNew Editorial for Problem #14130cqbzzlrView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.