The Wall (medium)

题意翻译

现在你有 $n$ 个砖和一个宽度为 $C$ 的场地。你可以想象成这个场地是一个高度无限，宽度为 $C$ 的矩形。 每个砖占据一个位置，这个位置记作'B'，没有砖块的地方记作 '.' 问最后可以摆出多少种不同的形状（'.'和'B'只要排列的不同就算不同方案），方案数 $\mod 1e6+3$

题目描述

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 HC $ ^{2} $ (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 $ 10^{6}+3 $ .

输入输出格式

输入格式

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

输出格式

Print the number of different walls that Heidi could build, modulo $ 10^{6}+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

说明

The number $ 10^{6}+3 $ is prime. In the second sample case, the five walls are: ``` <pre class="verbatim"><br></br> B B<br></br>B., .B, BB, B., and .B<br></br> ``` In the third sample case, the nine walls are the five as in the second sample case and in addition the following four: ``` <pre class="verbatim"><br></br>B B<br></br>B B B B<br></br>B., .B, BB, and BB<br></br> ```

题意翻译

现在你有 $n$ 个砖和一个宽度为 $C$ 的场地。你可以想象成这个场地是一个高度无限，宽度为 $C$ 的矩形。 每个砖占据一个位置，这个位置记作'B'，没有砖块的地方记作 '.' 问最后可以摆出多少种不同的形状（'.'和'B'只要排列的不同就算不同方案），方案数 $\mod 1e6+3$