Statement : E4. Graph Cutting (Three Vertices, Fixed Size)

After E3. Same as E1, but the three pinned vertices $a$, $b$, $c$ define a Steiner tree core instead of a single path. Count connected subgraphs $S$ with $\{a,b,c\}\subseteq S$ and $|S|=d$.

The final step E counts all triples under Fedya’s minimal-cut rule.

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

Each test case:

• One line: $n$, $d$, $a$, $b$, $c$ ($3 \le d \le n \le 2000$, distinct $a,b,c$).
• 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 $a$, $b$, and $c$, modulo $998244353$.

Input

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

Output

1
1
1
1

Note

• $(1,2,3)$, $d=3$: only $\{1,2,3\}$.
• $(1,2,3)$, $d=4$: only $\{1,2,3,4\}$.
• $(1,2,3)$, $d=3$ again: still $1$.
• $(2,3,4)$, $d=4$: Steiner core is the whole star (size $4$); no extras possible.

Compare with E on the same tree, $d=3$: valid triples for minimal cut are $(1,2,3)$, $(1,2,4)$, $(1,3,4)$ — three objects, not three subgraph counts.