Problem Statement

Consider the map $f_K(x)=\begin{cases}2^Kx^K&(0\leq x\leq 1/2)\\2^K(1-x)^K&(1/2\lt x\leq 1)\end{cases}\ (K\geq 1)$, whose domain and codomain are both $[0,1]$.

For a positive integer $N$, define $f_K^N(x)$ recursively by $f_K^1(x)=f_K(x),\ f_K^{n+1}(x)=(f_K\circ f_K^n)(x)\ (n\geq 1)$.

Given positive integers $K$ and $N$, find the number, modulo $998244353$, of real numbers $x$ satisfying all of the following conditions.

• $x\in [0,1]$
• $f_K^N(x)=x$
• For every positive integer $n$ less than $N$, $f_K^n(x)\neq x$

Input

$K\ N$

• All inputs are integers
• $1\leq K\leq 10^{18}$
• $1\leq N\leq 10^6$

Output

Print the number, modulo $998244353$, of real numbers $x$ satisfying all the conditions, followed by a newline.

Sample

2 1

3

1 6

54

1000000000000000000 1000000

970415685