B'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: 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 xe2 x80 x89+ xe2 x80 x893. The first line contains two space-separated integers n and C, 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89500000, 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89C xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89200000. Print the number of different walls that Heidi could build, modulo 106 xe2 x80 x89+ xe2 x80 x893. The number 106 xe2 x80 x89+ xe2 x80 x893 is prime. In the second sample case, the five walls are: In the third sample case, the nine walls are the five as in the second sample case and in addition the following four: '...