Consider a rooted, unlabeled tree where the order of subtrees is distinguished. Each node has two attributes: color and weight. Node colors are either red or blue, and node weights are positive integers. The following constraints apply:

• For a red node, the sum of the weights of its children must be equal to its own weight.
• For a blue node, its children must be blue nodes, and the sum of their weights must not exceed the node's own weight. A blue node may also have no children.
• If a blue node $u$ has a blue parent, then $u$ cannot have any children.

For specific details regarding these constraints, please refer to the sample explanations.

Let $f_{d,v}$ be the number of trees with depth at most $d$ and a root weight of $v$ that satisfy the above conditions. Given $n$ and $k$, for the series $$\sum_{i=1}^\infty \frac{f_{n,i}i^k}{(4n^n)^i}$$ if this series converges, output its convergent value modulo $998244353$ (it can be proven that the value is always a rational number); if the series diverges, output qwq.

Input

A single line containing two integers $n$ and $k$ ($1\le n\le 4\times 10^8$, $0\le k \le 5\times 10^5$).

Output

Output a single integer on one line, or the string qwq if the series diverges.

Examples

Input 1

1 2

Output 1

628524223

Input 2

2 1

Output 2

325957340

Input 3

6 3

Output 3

227812422

Input 4

10 15

Output 4

75178386

Input 5

233 23

Output 5

779183524

Note

For the first sample:

Here $n=1$, meaning the tree depth is at most $1$. The tree can only consist of a single node, the root. However, the root cannot be red because it would not satisfy property $1$. Thus, $f_{1,i}=1 \ (i\geq 1)$. Therefore, the answer is

$$\sum_{i=1}^\infty \frac{ i^2}{4^i}=\frac{20}{27}$$ Modulo $998244353$, this is $628524223$.

For the second sample:

Here $n=2$. Through derivation, it can be found that $f_{2,i}=3\times 2^{i-1}$. The answer is $$\sum_{i=1}^\infty \frac{(3\times 2^{i-1})i}{16^i}=\frac{12}{49}$$

For example, for $i=3$ (values represent node weights, colors represent node colors):

• If the root is red, its children can be $(\color{blue}{1}\color{black},\color{blue}{1}\color{black},\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})$, or $(\color{blue}{3}\color{black})$.
• If the root is blue, in addition to the $4$ cases above, its children can be $(\color{blue}{1}\color{black},\color{blue}{1}\color{black})$, $(\color{blue}{2}\color{black})$, $(\color{blue}{1}\color{black})$, or it may have no children.

There are $12$ types in total, consistent with $f_{2,3}=3\times 2^2=12$.

For the third sample: The value before modulo is approximately $5.8984784\times 10^{-5}$.

Note 1

Two rooted, unlabeled trees $T_1$ and $T_2$ (where subtree order is distinguished) are identical if and only if:

• The root nodes of $T_1$ and $T_2$ have the same weight and color;
• The root nodes of $T_1$ and $T_2$ have the same number of subtrees, denoted by $m$;
• The subtrees $a_1,\dots,a_m$ of the root of $T_1$ are identical to the subtrees $b_1,\dots,b_m$ of the root of $T_2$, respectively.

This recursively defines whether two trees are identical.

Note 2

For a sequence of positive numbers $a_1, a_2, \dots$, if there exists a real number $S$ such that for any $\epsilon>0$, there exists a positive integer $N$ where for all $n\geq N$: $$S-\sum_{i=1}^na_i<\epsilon$$ then the positive series $\sum_{i=1}^\infty a_i$ is said to converge, and $S$ is defined as its convergent value. It can be proven that if $S$ exists, it is unique. If no such $S$ exists, the series is said to diverge.