题目背景

忽如一夜春风来，千树万树梨花开。

雪，覆盖了大漠上的一颗颗树，仿佛朵朵梨花盛开。但是令 krjt 意想不到的是，这些树居然真的是梨树！

题目描述

给你一颗以 $1$ 为根的树，初始时每个点都是白色，每个点有两个权值 $a_i,b_i$，初始时所有点的两个权值都为 $0$，但 $a_1=k$。

我们通过如下操作定义一个序列 $\{v_t\}$ 的权值：

• 从小到大度过 $1,2,3,\dots,t$ 这 $t$ 个时刻。
• 在第 $x$ 个时刻，对于 $i\in[1,n]$，执行 $b_i\gets b_i+v_x$。
• 对于父子 $(u,v)$，设 $u$ 为父亲，可以选定整数 $h\in[0,a_u]$ 执行操作 $a_u\gets a_u-h$，$a_v\gets a_v+h$，之后该时刻内形如 $(v,w)$ 且 $v$ 为父亲的父子不能操作。
• 若一个点 $i$ 满足 $a_i+b_i<0$，将 $i$ 以及 $i$ 的子树中的点染成黑色。
• 执行最优操作以最大化第 $t$ 时刻后的白点个数，该序列权值即为最大白点个数。

定义一个序列 $\{v_t\}$ 合法仅当 $\forall i\in[1,t]$，$\lvert v_i\rvert\in[0,m]$。给定 $t$，求出所有合法序列 $\{v_t\}$ 的权值之和对 $998244353$ 取模的值。

原题面

krjt 的目光注视在一棵以 $1$ 号结点为根的，$n$ 个结点的梨树上。

这颗梨树的每个点在每一刻都可以做任意次以下操作：将自己的基本热量提供任意正整数量给某个儿子。

但需要注意的是，在同一个时刻里，只有当一个结点的所有儿子结束操作后，该结点才能操作。

雪纷纷地下着，梨树在 $t$ 个时刻的冬天里，第 $i$ 天所有操作完成后每个结点的都会加上 $v_i$ 点附加热量，若加上后该结点的总热量仍然 $<0$ 则会连同它的子树一起冻死（自动与其祖先断开，掉到地上）。每个 $v_i$ 都是 $[-m,m]$ 中的一个不确定的整数值。

梨树定义一个序列 $\{v_t\}$ 的价值为它作为每时刻增加的热量时，梨树最多保留的结点数。

梨树不愿在这个冬天死去，希望求出所有方案的价值和，以保留尽量多的结点迎接春天，绽放花朵。因为在冬天前，它的根结点储蓄了 $k$ 点基本热量（和 $0$ 点附加热量，其他结点储蓄了 $0$ 点热量），这是自知活不过冬天的伙伴给它的。

而它伙伴在最后一点意识隐隐消失时，仿佛能够看到：一夜春风轻抚，冰雪消融，树林里朵朵梨花开……

答案对 $998244353$ 取模。

输入格式

第一行四个非负整数 $n,m,t,k$，分别表示树的结点个数，$v_i$ 的取值范围，冬天的时长，根结点原本存储的热量。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u$ 号结点与 $v$ 号结点之间有一条边。

输出格式

输出所有 $(2m+1)^{t}$ 种情况的答案的和对 $998244353$ 取模后的结果。

1 1 1 1

3

3 1 2 2
1 2
1 3

22

5 2 3 5
1 2
2 3
2 4
4 5

407

10 5 6 44
1 2
1 3
2 5
2 6
3 4
6 7
6 8
4 9
9 10

10465095

提示

样例 $3$ 解释：

对于一种 $\{v_3\}=\{1,0,-2\}$ 的情况，一种最优操作如下：

• 第一个时刻，$1$ 号结点传递 $4$ 热量给 $2$ 号结点，操作完毕并增加 $v_1=1$ 后每个结点的热量分别为 $2,5,1,1,1$。
• 第二个时刻，$2$ 号结点传递 $2$ 热量给 $4$ 号结点，操作完毕并增加 $v_2=0$ 后每个结点的热量分别为 $2,3,1,3,1$。
• 第三个时刻，$2$ 号结点传递 $1$ 热量给 $3$ 号结点，$4$ 号结点传递 $1$ 热量给 $5$ 号结点，操作完毕并增加 $v_3=-2$ 后每个结点的热量分别为 $0,0,0,0,0$。
• 第四个时刻，冬天过去，$5$ 个结点全部存活。

样例 $4$ 解释：

对于一种 $\{v_{6}\}=\{1,2,1,2,1,2\}$ 的情况，一种最优操作如下：

• 每个时刻都不进行操作。
• 第 $7$ 个时刻，冬天过去，$5$ 个结点全部存活。

---

本题采用捆绑测试。

Subtask 编号	$n \le$	$m \le$	$t \le$	$k \le$	分值
$0$	$4$			$40$	$20$
$\color{red}1$	$\color{red}2 \times 10^5$	$\color{red}20$		$\color{red}1 \times 10^5$	$\color{red}10$
$2$	$2 \times 10^5$	$20$		$3 \times 10^5$	$20$
$3$		$50$	$100$		$10$
$4$			$500$		$40$

特殊性质：对于 Subtask 1，保证树的形态是菊花。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq k\leq 3\times 10^5$，$1\leq m\leq 50$，$1\leq t\leq 500$，保证输入构成一棵树。