※前問を解いていない方はそちらから解くことをお勧めします。
問題文
コマがx軸上の原点に置いてあります。あなたはこの後、以下の操作を何度も繰り返します。
操作:1からmまでの数字が全て等確率で出るサイコロを振り、出た目の数だけコマをx軸の正の方向に進める。
この操作の途中でちょうど点nに止まる確率をmod 998244353で求めて下さい。
注意:求める確率が既約分数p/qで表されるとき、rq≡p(mod 998244353)かつ
0≤r<998244353を満たす整数rがこの問題の制約のもとで一意に定まります。このrが求める値です。
制約
- 入力は全て整数
- 2≤m≤100
- 1≤n≤1018
入力
入力は以下の形式で与えられます。
出力
結果を1行に出力して下さい。
サンプル
最初に1を出せば良いので、求める確率は1/2となります。答えは2r≡1(mod998244353)かつ
0≤r<998244353を満たす
r=499122177となります。
1回目に2を出すか、もしくは1回目に1を出し、2回目ににもう一度1を出せば良いです。
よって、求める確率は1/6+(1/6)2=7/36なので、答えは36r≡7(mod998244353)かつ
0≤r<998244353を満たす
r=27729010となります。
入力3
100 1000000000000000000
前問と同じ解法で求められるとは限りません。