CF690D2 The Wall (medium)

Heidi the Cow 惊呆了：北方的城墙出现了裂缝？僵尸正在外面集结，组成队伍，准备进攻？这绝不能发生！她赶紧拿出她的 HC $^{2}$（疯狂建造手册），并翻到正确的章节： 如何建造一堵墙： 1. 取一组砖块。 2. 选择一种可能的墙体设计。计算可能的设计数量留作读者练习。 3. 按照选定的设计，将砖块一块块叠放起来。 这看起来很简单。但 Heidi 是一头会编程的奶牛，不是会建造的奶牛。她的思绪总是回到第 2 步。尽管僵尸即将来袭，她还是想知道，最多用 $n$ 块砖，她究竟能建造多少种不同的墙。 一堵墙由若干墙段组成，定义同简单版。问用至少 $1$ 块、至多 $n$ 块砖能建造多少种不同的墙？如果存在某一列 $c$ 和某一行 $r$，使得一堵墙在该位置有砖而另一堵墙没有，则这两堵墙视为不同。 你将得到 $n$ 和 $C$，其中 $C$ 表示墙的宽度（定义同简单版）。请输出不同墙的数量，对 $10^{6}+3$ 取模。

第一行包含两个用空格分隔的整数 $n$ 和 $C$，$1 \leq n \leq 500000$，$1 \leq C \leq 200000$。

输出 Heidi 能建造的不同墙的数量，对 $10^{6}+3$ 取模。

数 $10^{6}+3$ 是质数。 在第二个样例中，五种墙分别是： ``` B B B., .B, BB, B., 和 .B ``` 在第三个样例中，九种墙包括第二个样例的五种，以及另外四种： ``` B B B B B B B., .B, BB, 和 BB ``` 由 ChatGPT 4.1 翻译