H - Sugoroku Loop

配点 : 200点

個のマス目があるすごろくがあります。
マス目は順に の番号が付けられており、マス目 から へ移動することができます。
さらにこのすごろくは環状になっており、マス目 から へ移動することができます。
つまり、 の順にマスを進むことができます。
あなたは最初マス目 にいます。今から 1, 2, 3, 4, 5, 6 の目が出るサイコロを振り、出た目の数だけマスを進むことを丁度 回繰り返します。
回の移動後、マス目 にいるとあなたは嬉しくなります、そのようなサイコロの出目の出方は何通りありますか。
答えを で割った余りで出力してください。

入力は以下の形式で標準入力から与えられる。

答えを出力してください。

5 2

7

サイコロの出目が

のとき、マス目 に丁度たどり着きます。
マスが環状になっていることに気をつけてください。

100 10

0

31 415

524620511

で割った余りで出力してください。