CF690D2.The Wall (medium)

Heidi the Cow is aghast: cracks in the northern Wall? Zombies gathering outside, forming groups, preparing their assault? This must not happen! Quickly, she fetches her HC2 (Handbook of Crazy Constructions) and looks for the right chapter:

How to build a wall:

1. Take a set of bricks.
2. Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.
3. Place bricks on top of each other, according to the chosen design.

This seems easy enough. But Heidi is a Coding Cow, not a Constructing Cow. Her mind keeps coming back to point 2b. Despite the imminent danger of a zombie onslaught, she wonders just how many possible walls she could build with up to n bricks.

A wall is a set of wall segments as defined in the easy version. How many different walls can be constructed such that the wall consists of at least 1 and at most n bricks? Two walls are different if there exist a column c and a row r such that one wall has a brick in this spot, and the other does not.

Along with n, you will be given C, the width of the wall (as defined in the easy version). Return the number of different walls modulo 106 + 3.

奶牛海蒂惊呆了：北墙出现了裂缝？僵尸正在墙外集结，组成队伍，准备发起进攻？这绝不能发生！她迅速取出了自己的《疯狂建筑手册》（HC2），翻到正确的一章：

如何建造一堵墙：

1. 准备一组砖块。
2. 从所有可能的墙体设计方案中选择一种。计算可能的设计方案总数留作读者练习。
3. 按照所选设计方案，将砖块逐层叠放。

这看起来相当简单。但海蒂是一头编程牛，而非建造牛。她的思绪却总回到第 2 步的子步骤 b 上。尽管僵尸大军压境的危机迫在眉睫，她仍不禁思索：用至多 $n$ 块砖，她究竟可以建造出多少种不同的墙体？

墙体定义同“简单版本”中的墙体段集合。问：由至少 $1$ 块、至多 $n$ 块砖构成的墙体，总共能构造出多少种互不相同的墙体？若存在某一列 $c$ 和某一行 $r$，使得其中一堵墙在此位置有砖块而另一堵墙没有，则称这两堵墙不同。

除输入 $n$ 外，你还将得到 $C$（即墙体的宽度，定义同“简单版本”）。请输出不同墙体的总数对 $10^6 + 3$ 取模的结果。

The first line contains two space-separated integers n and C, 1 ≤ n ≤ 500000, 1 ≤ C ≤ 200000.

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

Print the number of different walls that Heidi could build, modulo 106 + 3.

输出海蒂可以建造的不同墙壁的数量，对 $10^6 + 3$ 取模。

The number 106 + 3 is prime.

In the second sample case, the five walls are:

B B
B., .B, BB, B., and .B

In the third sample case, the nine walls are the five as in the second sample case and in addition the following four:

B B
B B B B
B., .B, BB, and BB

数字 $10^6 + 3$ 是质数。

在第二个样例中，五堵墙分别是：

B B
B., .B, BB, B., 和 .B

在第三个样例中，九堵墙包括第二个样例中的五堵，以及以下额外的四堵：

B B
B B B B
B., .B, BB, 和 BB