Universal Cup Judging System

Universal Cup

Süre Sınırı: 8.0 s Bellek Sınırı: 256 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Aleksei received an apple tree of size $n$ as a birthday present. As a competitive programmer himself, he decided to calculate the number of $k$-apple pies on the tree.

An apple tree of size $n$ is defined as a rooted tree with $n$ vertices, rooted at vertex $1$, where each vertex has strictly fewer direct children than its parent (except the root that doesn't have any parent).

A $k$-apple pie is a pair $(v, S)$ where:

  • $v \in V$ is a vertex of the tree (the center),
  • $S \subset V \setminus \{v\}$ is a set of vertices of size $k - 1$,
  • there exists an integer $d$ such that for every $u \in S$, $\text{dist}(v, u) = d$.

The distance $\text{dist}(u, v)$ is defined as the number of edges on the simple path between vertices $u$ and $v$.

In other words, a $k$-apple pie consists of one vertex $v$ (the center) and $k - 1$ other vertices that are all at the same distance from $v$.

Your task is to compute the number of $k$-apple pies in the given tree.

Since the answer may be large, output it modulo $998\,244\,353$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case begins with a line containing two integers $n$ and $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): the number of vertices in the apple tree and the size of the apple pie.

The next line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), where $p_i$ denotes the parent of vertex $i$ in the apple tree.

The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a single integer: the number of $k$-apple pies modulo $998\,244\,353$.

Examples

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

In the first test case, the only existing pie is centered at vertex $1$, and the corresponding set is $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.