配点
- 満点
- 140
- 部分点1
- 20
- 部分点2
- 40
問題文
当尝试乘坐平时上下班乘的电车的相反方向时,车内很空,感觉非常好。这列电车会开到哪里呢……偶然看到窗外整齐排列的电线杆群时,感觉那里似乎站着忍者。
电线杆沿数轴的整数点排列。最初从车窗看,左端为坐标0H看到连续排列的电线杆。在时刻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