Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Kyoto University has a magnificent symbolic tree as its symbol tree.

Impressed by this symbolic tree, K-kun made a copy of it as a rooted tree with $N$ vertices.

The vertices of the tree are labeled $1, 2, \dots, N$, the root of the tree is vertex $1$, and the $i$-th edge connects vertices $u_i$ and $v_i$.

Thinking that merely copying the tree would be uninteresting, K-kun writes a non-negative integer on each vertex of the tree so that the following conditions are satisfied.

Conditions

  • The integer written on the root is $K$.
  • For each vertex other than the root, the integer written on that vertex is at most the integer written on its parent.

Find the remainder when the number of possible ways to write integers on the vertices of the tree is divided by $998244353$.

Two ways of writing integers on the vertices are considered different if and only if there exists some vertex such that the integer written on that vertex is different.

Input

The first line contains integers $N, K$ separated by spaces. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Each of the following $N - 1$ lines contains integers $u_i, v_i$ separated by spaces, representing an edge of the tree.

Output

Output the answer modulo $998244353$.

Examples

Sample Input 1

5 1
1 2
1 3
3 4
3 5

Sample Output 1

10

Sample Input 2

16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1

Sample Output 2

623173536

Note

For the first example, the following $10$ assignments of integers to vertices $1, 2, 3, 4, 5$ satisfy the conditions.

  • $1, 0, 0, 0, 0$
  • $1, 0, 1, 0, 0$
  • $1, 0, 1, 0, 1$
  • $1, 0, 1, 1, 0$
  • $1, 0, 1, 1, 1$
  • $1, 1, 0, 0, 0$
  • $1, 1, 1, 0, 0$
  • $1, 1, 1, 0, 1$
  • $1, 1, 1, 1, 0$
  • $1, 1, 1, 1, 1$

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1528EditorialOpen题解jianglyView

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.