P10037 "FAOI-R2" Frost and Snow for a Thousand Years

> Looking back on this old street, in the mist and clouds I trace who I am. > Just a few drops of evening rain are enough to cover up right and wrong. > When the moonlight surges, who will gently knock on this door? > Moss-green bluestone slabs, mottled with years flowing like water. > A few small cups of wine, yet the tangled knot cannot be sorted out. > In your indifferent brows, I glimpse the joys and sorrows of those who part, frosted by snow. Luo Tianyi sees a pear tree in the snow. There is limited energy in the root of the pear tree, and it can transmit energy upward to other nodes. But the wind and snow are heavy: at every moment, the energy at each node may increase or decrease, and nodes with too little energy will fall off.

Specifically, this pear tree can be abstracted as a tree rooted at node $1$. Initially, every node is white. Each node has energy $a_i$. Initially, the energy of all nodes except $1$ is $0$, and $a_1=k$. We define an accumulated energy $b$. We define the value of a sequence $\{v_t\}$ through the following process: - Pass through the $t$ moments $1,2,3,\dots,t$ in increasing order. - At moment $x$, perform $b\gets b+v_x$. - For an edge $(u,v)$ in the tree, with $u$ as the parent, you may choose an integer $h\in[0,a_u]$ and perform $a_u\gets a_u-h$, $a_v\gets a_v+h$. After that, within this moment, edges of the form $(v,w)$ where $v$ is the parent cannot be operated on. - If a node $i$ satisfies $a_i+b

The first line contains four non-negative integers $n,m,t,k$, representing the number of nodes in the tree, the range of values of $v_i$, the number of moments, and the initial value of $a_1$, respectively. The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between node $u$ and node $v$.

Output the sum of the values of all valid sequences modulo $998244353$.

**[Sample #3 Explanation]** For one case $\{v_3\}=[1,0,-2]$, one optimal set of operations is as follows: - At the first moment, node $1$ transfers $4$ energy to node $2$. After the operation, $a=[1,4,0,0,0]$, $b=1$. - At the second moment, node $2$ transfers $2$ energy to node $4$. After the operation, $a=[1,2,0,2,0]$, $b=1$. - At the third moment, node $2$ transfers $1$ energy to node $3$, and node $4$ transfers $1$ energy to node $5$. After the operations, $a=[1,1,1,1,1]$, $b=-1$. - After all moments end, since there is never any node with $a_i+b