Can you stop exactly? 2

2 secs 1024 MB
YSatUT's icon YSatUT

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

問題文

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

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

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

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

制約

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

入力

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

m n

出力

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

サンプル

入力1
2 1
出力1
499122177

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


入力2
6 2
出力2
27729010

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


入力3
100 1000000000000000000
出力3
408263602

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


提出


Go (1.21)