Can you stop exactly? 2

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

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

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

この操作の途中でちょうど点に止まる確率をで求めて下さい。

注意：求める確率が既約分数で表されるとき、かつ を満たす整数がこの問題の制約のもとで一意に定まります。このが求める値です。

• 入力は全て整数

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

m n

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

2 1

499122177

最初にを出せば良いので、求める確率はとなります。答えはかつ を満たす となります。

6 2

27729010

回目にを出すか、もしくは回目にを出し、回目ににもう一度を出せば良いです。 よって、求める確率はなので、答えはかつ を満たす となります。

100 1000000000000000000

408263602

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