Adding Sequences#4200
Given an integer sequence \{a_n\} of length , consisting of non-negative numbers, we derive a new sequence \{b_n\} of length n-1 using the following rule:
b_i = a_i + a_{i+1}.
By applying this transformation n-1 times, we eventually reduce the sequence to a single number, denoted as .
The task is to determine how many integer sequences of length with non-negative elements will result in the number after performing the described procedure.
The input consists of two integers: (0 \leq k \leq 50000) and (2 \leq n \leq 50000).
Output a single integer, which is the number of integer sequences of length with non-negative elements that result in the number after the described procedure. The result should be given modulo 10^6.
Example 1