配点

満点

140

部分点1

20

部分点2

40

問題文

いつも乗る通勤電車をいつもと逆の方向に乗ってみると、車内が空いていてとても気分が良い。この電車はどこまでいくのだろう・・・ふと窓の外に規則正しく並んでいる電柱群を見るとそこに忍者が立っているような気がした。

数直線の整数点上に電柱が並んでいる。はじめ車窓からは座標0を左端としてH本の電柱が連続して見えている。時刻0のときに忍者が座標0の電柱の上に立っている。時刻0から開始して、次の規則で状況が動く。

• 忍者が電柱に立っているときは、かならず車窓のうつす範囲内にいなければならない。
• 車窓から見える範囲は速度1で数直線の正の向きに進む。
• 忍者が整数時刻に電柱に立っているならば、時間[\sqrt{D}]だけかけて、数直線で正の向きにD個先の電柱にジャンプするか、その場で姿を消すかのいずれかを行う。ただし[x]は、x以下で最大の整数を表す。
• Dは正の整数である。
• ジャンプをはじめたら、着地するまでは滞空している。
• 姿を消したらそれ以降については2度と現れず、他の制約を満たす必要もなくなる。

時刻Tで忍者は消えていて滞空もしていなかった。忍者が条件を満たしながら移動する組合せの個数を1000003で割った余りを求めよ。なお忍者は時刻0およびTで消えることも可能とする。

入力例 1

1 2345

出力例 1

2346

忍者がジャンプするなら1本ごとしか行えないためどの時刻で離脱する組合せも1通りずつ、あわせて2345+1=2346通り。

入力例 2

3 1

出力例 2

4

0, 0->1, 0->2, 0->3 の4通り

入力例 3

3 2

出力例 3

11

入力例 4

20 70300

出力例 4

8512