配点

满分

140

部分分数1

20

部分分数2

40

---

问题描述

当我试着乘坐平常的通勤列车朝相反的方向行驶时，车厢很空，感觉非常好。不知道这趟列车会开到哪里去……突然，我看到窗外整齐排列的电线杆上站着忍者。

数轴上排列着整数坐标的电线杆。一开始，从车窗中可以看到以坐标0为起点连续可见$H$根电线杆。时刻0时，忍者站在坐标0的电线杆上。从时刻0开始，根据以下规则进行移动：

• 当忍者站在电线杆上时，必须始终位于车窗的可见范围内。

• 车窗可见范围相对于数轴正向以速度1向前移动。

• 如果忍者在整数时刻站在电线杆上，则经过时间\[\\sqrt{D}\]，沿着数轴正向跳跃$D$个电线杆或者消失。其中\[x\]表示不超过$x$的最大整数。

• $D$是正整数。

• 跳跃开始后，在着陆前悬空。

• 如果消失，则之后不再出现，也不需要满足其他约束。

时刻$T$时，忍者消失并且没有悬空。求满足条件的忍者移动方案的数量除以$1000003$后的余数。忍者可以在时刻$0$和$T$消失。

---

输入格式

输入以以下格式给出。

$H\\ T$

输出格式

输出移动方案的数量，结果在一行中输出。

约束条件

• $1 ≤ H ≤ 77$
• $0 ≤ T ≤ 777777777$
• 输入均为整数。

以上为基本约束条件。

该问题有一个组包含20个分值的测试用例。该组的测试用例除了满足基本约束条件外，还满足以下约束条件。

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

该问题有一个组包含40个分值的测试用例。该组的测试用例除了满足基本约束条件外，还满足以下约束条件。

• $1 ≤ H ≤ 22$

---

输入示例 1

1 2345

输出示例 1

2346

由于忍者每次只能跳一根电线杆，所以在任何时刻离开的组合都只有一种，共2345+1=2346种。

---

输入示例 2

3 1

输出示例 2

4

有4种组合：0, 0→1, 0→2, 0→3。

---

输入示例 3

3 2

输出示例 3

11

---

输入示例 4

20 70300

输出示例 4

8512

---

出题人：uwi

---

来源

秋之祭