#P18043. The Symbolic Tree

The Symbolic Tree

The Symbolic Tree

题目描述

给定一棵有 NN 个顶点的树,顶点编号为 1,…,N1,\ldots,N,以顶点 11 为根。你要在每个顶点上写一个非负整数,满足:

  • 根上写的整数恰好为 KK;
  • 每个非根顶点上的整数不大于它父亲上的整数。

求合法填写方案数,对 998244353998244353 取模。只要至少一个顶点上的整数不同,就认为两种方案不同。

输入格式

第一行两个整数 N,KN,K。

接下来 N−1N-1 行,每行两个整数 ui,viu_i,v_i,表示一条无向边。输入保证这些边构成一棵树。

2≤N≤30002\le N\le3000,1≤K≤1091\le K\le10^9,1≤ui,vi≤N1\le u_i,v_i\le N。

输出格式

输出合法方案数对 998244353998244353 取模的结果。

样例 1

输入:

5 1
1 2
1 3
3 4
3 5

输出:

10

样例 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

输出:

623173536