该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

熊大为了保卫狗熊岭，要在森林里建立一个由 $n$ 个通信基站组成的预警网络。这 $n$ 个基站由 $n-1$ 条隐蔽的光缆连接，形成了一棵树的结构。

为了保证信号畅通，熊大需要为每个基站分配一个运行频率。频率可以选择从 $1$ 到 $m$ 之间的任意整数。

然而，频率 $k$ 是一个“高功率特殊频率”。由于高功率频率之间会互相干扰，且对周围低功率设备有压制作用，光头强的探测器很容易发现异常。为了安全，熊大设定了以下规则：

1. 整个网络中，最多只能有 $x$ 个基站被分配到频率 $k$ 。
2. 如果某个基站被分配了频率 $k$ ，那么与它通过光缆直接相连的所有相邻基站的频率必须严格小于 $k$ 。

熊大想知道，一共有多少种合法的频率分配方案？两种方案被认为是不同的，当且仅当至少有一个基站被分配了不同的频率。

由于答案可能很大，请将结果对 $998244353$ 取模的结果告诉熊大。

输入格式

输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

对于每组测试数据：
第一行包含四个整数 $n,m,k,x$ ，分别表示基站的数量、可选频率的上限、高功率特殊频率的值，以及最多允许分配频率 $k$ 的基站数量。

接下来 $n-1$ 行，每行包含两个整数 $u,v$ ,表示基站 $u$ 和基站 $v$ 之间有一条光缆连接。

输出格式

对于每组测试数据，输出一行一个整数，表示合法的频率分配方案数对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

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

输出 #1

13
35

说明/提示

对于所有测试数据，保证 $1 \leq T \leq 10 ,1 \leq n \leq 3000,1\leq x \leq 3000,1 \leq k \leq m \leq 10^9,1\leq u,v \leq n$ 。

此外，所有测试数据的 $n$ 之和不超过 $10000$ 。

特殊性质A： $\exists c$ ，使得所有基站都与 $c$ 直接相连。

特殊性质B：保证与每个基站直接相连的基站数量不超过 $2$ 。