Statement : E1. Graph Cutting (Two Vertices, Fixed Size)

Next step after E0. Triplet analogues: E3 → E4 → E.

You are given a tree with $n$ vertices, an integer $d$, and distinct vertices $a$ and $b$. Count connected subgraphs $S$ such that:

• $\{a,b\}\subseteq S$, and
• $|S| = d$.

The first line contains an integer $t$ ($1 \le t \le 500$).

Each test case:

• One line: $n$, $d$, $a$, $b$ ($2 \le d \le n \le 2000$, $1 \le a, b \le n$, $a \ne b$).
• Then $n - 1$ lines: tree edges.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

For each test case, print the number of connected subgraphs of size exactly $d$ that contain both $a$ and $b$, modulo $998244353$.

Input

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

Output

1
1
1
0

Note

• $n=4$, $d=3$, $a=2$, $b=3$: only $\{2,1,3\}$ works; adding leaf $4$ makes size $4$.
• $n=4$, $d=4$, $a=2$, $b=3$: only $\{2,1,3,4\}$.
• $n=5$, $d=5$, $a=1$, $b=5$: the whole tree is the only connected subgraph containing both.
• $n=4$, $d=3$, $a=2$, $b=4$: any connected set containing $2$ and $4$ has size at least $4$ on this star.