牛海蒂惊呆了:北墙出现裂缝?僵尸在外面聚集,形成群体,准备进攻?这绝不能发生!她很快拿起 HC2(疯狂构造手册)并寻找正确的章节:
如何建造一堵墙:
1. 取一组积木。
2. 选择一种可能的墙壁设计。计算可能的设计数量留给读者作为练习。
3. 根据所选设计,将积木相互叠放。
这看起来很简单。但海蒂是一头编码牛,而不是一头建筑牛。她的思绪不断回到第 2b 点。尽管僵尸袭击的危险迫在眉睫,她还是想知道自己可以用 n 块砖建造多少堵墙。
墙是简单版本中定义的一组墙段。可以建造多少种不同的墙,使得墙至少由 1 块、最多 n 块砖组成?如果存在 c 列和 r 行,并且一面墙在该位置有砖块,而另一面墙没有,则两面墙是不同的。
除了 n 之外,您还会得到 C,即墙的宽度(如简单版本中所定义)。返回不同墙的数量以 106 + 3 为模。
输入
第一行包含两个空格分隔的整数 n 和 C,1 ≤ n ≤ 500000,1 ≤ C ≤ 200000。
输出
打印 Heidi 可以建造的不同墙的数量,以 106 + 3 为模。
示例
输入 #1
5 1
输出 #1
5
输入 #2
2 2
输出 #2
5
输入 #3
3 2
输出 #3
9
输入#4
11 5
输出#4
4367
输入 #5
37 63
输出 #5
230574
注意
数字 106 + 3 是素数。
在第二个示例案例中,五堵墙是:
在第三个示例案例中,九个墙壁是第二个示例案例中的五个墙壁,另外还有以下四个: