题目描述

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.

3 1

15

6 2

17286

30 9

434031055

114514 2520

136362204

提示

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$.