※前問を解いていない方はそちらから解くことをお勧めします。

問題文

コマが$x$軸上の原点に置いてあります。あなたはこの後、以下の操作を何度も繰り返します。

操作：$1$から$m$までの数字が全て等確率で出るサイコロを振り、出た目の数だけコマを$x$軸の正の方向に進める。

この操作の途中でちょうど点$n$に止まる確率を${\rm mod}\ 998244353$で求めて下さい。

注意：求める確率が既約分数$p/q$で表されるとき、$rq≡p ({\rm mod}\ 998244353)$かつ $0≤r<998244353$を満たす整数$r$がこの問題の制約のもとで一意に定まります。この$r$が求める値です。

制約

• 入力は全て整数
• $2\leq m\leq 100$
• $1\leq n\leq 10^{18}$

入力

入力は以下の形式で与えられます。

m n

出力

結果を1行に出力して下さい。

サンプル

2 1

499122177

最初に$1$を出せば良いので、求める確率は$1/2$となります。答えは$2r≡1 ({\rm mod} 998244353)$かつ $0≤r<998244353$を満たす $r=499122177$となります。

6 2

27729010

$1$回目に$2$を出すか、もしくは$1$回目に$1$を出し、$2$回目ににもう一度$1$を出せば良いです。 よって、求める確率は$1/6+(1/6)^2=7/36$なので、答えは$36r≡7 ({\rm mod} 998244353)$かつ $0≤r<998244353$を満たす $r=27729010$となります。

100 1000000000000000000

408263602

前問と同じ解法で求められるとは限りません。