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:

- Take a set of bricks.
- Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.
- 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.

提交代码