Problem Background

Suddenly, as if by spring breeze overnight, thousands of trees and pear blossoms bloom.

Snow covers the trees in the desert, making them look like blooming pear blossoms. To krjt's surprise, these trees are actually pear trees!

Problem Description

You are given a tree rooted at node 1, where initially each node is white and has two values \(a_i\) and \(b_i\). Initially, all nodes have both values set to 0, except \(a_1 = k\).

We define the value of a sequence \(\{v_t\}\) through the following operations:
- Traverse through the moments \(1, 2, 3, \dots, t\) in ascending order.
- At moment \(x\), for \(i \in [1, n]\), update \(b_i \gets b_i + v_x\).
- For a parent-child pair \((u, v)\) where \(u\) is the parent, you can choose an integer \(h \in [0, a_u]\) to perform the operation \(a_u \gets a_u - h\), \(a_v \gets a_v + h\). After this operation, no further operations can be performed on pairs like \((v, w)\) where \(v\) is the parent in that moment.
- If a node \(i\) satisfies \(a_i + b_i < 0\), then node \(i\) and its subtree are colored black.
- Perform the optimal operations to maximize the number of white nodes, and the value of the sequence is the maximum number of white nodes.

A sequence \(\{v_t\}\) is considered valid if \(\forall i \in [1, t]\), \(\lvert v_i \rvert \in [0, m]\). Given \(t\), find the sum of the values of all valid sequences \(\{v_t\}\) modulo \(998244353\).

Input Format

The first line contains four non-negative integers \(n, m, t, k\), representing the number of nodes in the tree, the range of \(v_i\), the duration of winter, and the initial heat stored at the root node, respectively.

The next \(n-1\) lines each contain two positive integers \(u, v\), indicating an edge between node \(u\) and node \(v\).

Output Format

Output the sum of the values of all \((2m+1)^t\) possible scenarios modulo \(998244353\).

Sample Input and Output

Input Sample #1

1 1 1 1

Output Sample #1

3

Input Sample #2

3 1 2 2
1 2
1 3

Output Sample #2

22

Input Sample #3

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

Output Sample #3

407

Input Sample #4

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

Output Sample #4

10465095

Notes

This problem is bundled with subtasks.

Special Property: For Subtask 1, the tree is guaranteed to be a菊花 (a star topology).

For 100% of the data, \(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\), and the input forms a tree.

见题面 Input 部分

见题面 Output 部分