Монгол хэлээр
In English
По-Русски
Сайтын тухай
Тэмцээнүүд
Бодлогууд
Чансаа
Орчуулгын саналууд (209)
mn/690-D2
com/690-D2
Хадгалах
Fullscreen
# 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
Гаралт
5
Оролт
2 2
Гаралт
5
Оролт
3 2
Гаралт
9
Оролт
11 5
Гаралт
4367
Оролт
37 63
Гаралт
230574
Тэмдэглэл