Додавання послідовностей#4200
Нехай задано деяку цілочисельну послідовність {a_n} довжини , що складається з невід'ємних чисел. Сформуємо з неї послідовність {b_n} довжини n-1 за наступним правилом:
b_i = a_i + a_{i+1}.
Провівши таке перетворення n-1 раз, ми отримаємо послідовність довжини , тобто одне число, яке позначимо через .
Вам потрібно розв'язати наступну задачу – знаючи число , визначити, скільки цілочисельних послідовностей довжини з невід'ємними членами дають число в результаті вищеописаної процедури.
Два цілих числа (0 \leq k \leq 50000) і (2 \leq n \leq 50000).
Одне ціле число, взяте за модулем 10^6, – кількість цілочисельних послідовностей довжини з невід'ємними членами, які в результаті вищеописаної процедури дають число .
Приклад 1