题目描述

一个有根、无标号，但区分子树顺序的有根树，每个节点都有两种属性：颜色 与 权值。节点颜色分为红色和蓝色，节点权值是正整数。另外有以下限制：

• 对于红色节点，其所有儿子节点的权值之和必须与其相等。
• 对于蓝色节点，其儿子只能是蓝色节点，且权值和不大于它。蓝色节点也可以没有子节点。
• 如果一个蓝色节点 $u$ 的父节点也是蓝色，则 $u$ 不能有子节点。

关于对限制的具体说明，可以参见样例解释。

设 $f_{d,v}$ 表示深度不超过 $d$、根节点权值为 $v$、符合以上条件的树的数量。给定 $n,k$，对于级数 $$\sum_{i=1}^\infty \frac{f_{n,i}i^k}{(4n^n)^i}$$ 若此级数收敛，则输出其收敛值对 $998244353$ 取模的结果（可以证明其必然为有理数）；若此级数发散，则输出 qwq。

输入格式

输入一行两个整数 $n,k$（$1\le n\le 4\times 10^8$，$0\le k \le 5\times 10^5$）。

输出格式

输出一行一个整数，或一行一个字符串 qwq 表示答案。

样例

样例输入 1

1 2

样例输出 1

628524223

样例输入 2

2 1

样例输出 2

325957340

样例输入 3

6 3

样例输出 3

227812422

样例输入 4

10 15

样例输出 4

75178386

样例输入 5

233 23

样例输出 5

779183524

样例解释

对于第一组样例：

此时 $n=1$，即树的深度不超过 $1$，此时整个树只能有一个节点，即根节点。但根节点不能是红色，因为这样不满足性质 $1$。故 $f_{1,i}=1 \ (i\geq 1)$。所以答案为

$$\sum_{i=1}^\infty \frac{ i^2}{4^i}=\frac{20}{27}$$ 在模 $998244353$ 意义下为 $628524223$。

对于第二组样例：

此时 $n=2$，经过一些推导可以发现 $f_{2,i}=3\times 2^{i-1}$，此时答案为 $$\sum_{i=1}^\infty \frac{(3\times 2^{i-1})i}{16^i}=\frac{12}{49}$$

比如对于 $i=3$（数值表示对应节点权值，数字的颜色表示节点的颜色）：

• 若根为红色，其子节点可以分别是 $(\color{blue}{1}\color{black},\color{blue}{1},\color{blue}{1}\color{black}{)}$，$(\color{blue}{1}\color{black},\color{blue}{2}\color{black}{)}$，$(\color{blue}{2}\color{black},\color{blue}{1}\color{black}{)}$，$(\color{blue}{3}\color{black}{)}$。
• 若根为蓝色，其子节点除了以上 $4$ 种，还可以是 $(\color{blue}{1}\color{black},\color{blue}{1}\color{black}{)}$，$(\color{blue}{2}\color{black}{)}$，$(\color{blue}{1}\color{black}{)}$，或没有子节点。

一共是 $12$ 种，符合 $f_{2,3}=3\times 2^2=12$。

对于第三组样例： 取模前的答案约为 $5.8984784\times 10^{-5}$。

提示 1

定义两个有根、无标号，但区分子树顺序的有根树 $T_1,T_2$ 是相同的，当且仅当：

• $T_1$ 和 $T_2$ 的根节点权值与颜色相同；
• $T_1$ 和 $T_2$ 的根节点有相同的子树个数，记为 $m$；
• $T_1$ 根节点的子树 $a_1,\cdots,a_m$ 分别和 $T_2$ 根节点的子树 $b_1,\cdots,b_m$ 相同。

由此就递归定义了两个树是否相同。

提示 2

对于正数数列 $a_1,a_2,\cdots$，若存在一个实数 $S$，使得任意 $\epsilon>0$，都可以找到一个正整数 $N$，对于所有 $n\geq N$ 都有 $$S-\sum_{i=1}^na_i<\epsilon$$ 则称正项级数 $\sum_{i=1}^\infty a_i$ 收敛，并定义 $S$ 是它的收敛值，可以证明若 $S$ 存在则它是唯一的。 若不存在这样的 $S$，则称此级数发散。