← 返回题目列表

Codeforces · 690/D2

D2. 墙(中)

中文机器翻译题面 查看原题

牛海蒂惊呆了:北墙出现裂缝?僵尸在外面聚集,形成群体,准备进攻?这绝不能发生!她很快拿起 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 是素数。

在第二个示例案例中,五堵墙是:

在第三个示例案例中,九个墙壁是第二个示例案例中的五个墙壁,另外还有以下四个: