P14454 [ICPC 2025 Xi'an R] Heart of Darkness

For a tree $T$, define $v(T)$ as the number of schemes that stain vertices of $T$ in black and white, and satisfy the following conditions: - For all black vertices $u,v$ in $T$, vertices in the simple path from $u$ to $v$ are all black. - There are at least $k$ undirected edges $(u,v)$ satisfy $u$ and $v$ has different color. For all $n$ vertices labeled unrooted tree $T$, calculate the sum of $v(T)$ modulo $998244353$.

A single line contains two positive integers $n,k$ ($1\le n \le 10^7$, $1\le k \le 5000$).

A single integer as the answer.

For the first test case, there are only $3$ different $T$ those are chains, so they have the same $v(T)$. Denote $0$ as black and $1$ as white, there are $5$ schemes: $(0,0,1),(1,0,0),(1,1,0),(0,1,1),(1,0,1)$. We emphasize that schemes $(1,1,1)$ and $(0,0,0)$ don't satisfy the second condition, and $(0,1,0)$ doesn't satisfy the first one. Therefore, the answer is $3 \cdot 5 = 15$.