問題文

始域と終域がともに $[0,1]$ である写像 $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)$ を考えます。

また、正の整数 $N$ について、 $f_K^N(x)$ を $f_K^1(x)=f_K(x),\ f_K^{n+1}(x)=(f_K\circ f_K^n)(x)\ (n\geq 1)$ で再帰的に定義します。

正の整数 $K$ と $N$ が与えられるので、以下の条件を全て満たす実数 $x$ の個数を $998244353$ で割った余りを求めてください。

• $x\in [0,1]$
• $f_K^N(x)=x$
• 任意の $N$ より小さい正の整数 $n$ について、 $f_K^n(x)\neq x$

入力

$K\ N$

• 入力は全て整数
• $1\leq K\leq 10^{18}$
• $1\leq N\leq 10^6$

出力

条件を全て満たす実数 $x$ の個数を $998244353$ で割った余りを出力し、最後に改行してください。

サンプル

2 1

3

1 6

54

1000000000000000000 1000000

970415685