690D2 орчуулах · Codeforces.mn

# 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 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$.

## Тэмдэглэл
The number $10^{6} + 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

-- [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт

5 1

Гаралт

Оролт

2 2

Гаралт

Оролт

3 2

Гаралт

Оролт

11 5

Гаралт

Оролт

37 63