配点

満点

140

部分点1

20

部分点2

40

---

問題文

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

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

• 忍者が電柱に立っているときは、かならず車窓のうつす範囲内にいなければならない。

• 車窓から見える範囲は速度1で数直線の正の向きに進む。

• 忍者が整数時刻に電柱に立っているならば、時間\[\\sqrt{D}\]だけかけて、数直線で正の向きに$D$個先の電柱にジャンプするか、その場で姿を消すかのいずれかを行う。ただし\[x\]は、$x$以下で最大の整数を表す。

• $D$は正の整数である。

• ジャンプをはじめたら、着地するまでは滞空している。

• 姿を消したらそれ以降については2度と現れず、他の制約を満たす必要もなくなる。

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

---

入力形式

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

$H\\ T$

出力形式

組合せの個数を1行に出力せよ。

制約

• $1 ≤ H ≤ 77$
• $0 ≤ T ≤ 777777777$
• 入力値はすべて整数である。

以上を基本制約とする。

この問題の判定には、20 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは基本制約に加えて下記の制約も満たす。

• $1 ≤ H ≤ 22$
• $0 ≤ T ≤ 22222$

この問題の判定には、40 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは基本制約に加えて下記の制約も満たす。

• $1 ≤ H ≤ 22$

---

入力例 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

---

Writer: uwi

---

Source Name

Autumn Fest

---