Додавання послідовностей

Нехай задано деяку цілочисельну послідовність {a_n} довжини n, яка складається з невід'ємних чисел. Сформуємо з неї послідовність {b_n} довжини n–1 за наступним правилом:

b_i = a_i + a_i_{+1}.

Провівші таке перетворення n–1 раз, ми отримаємо послідовність довжини 1, тобто одне число, яке позначимо через k.

Вам потрібно розв'язати наступну задачу – знаючи число k, визначте, скільки цілочисельних послідовностей довжини n з невід'ємними членами дають число k у результаті вищшеописаної процедури.

Вхідні дані

Два цілих числа k (0 ≤ k ≤ 50000) і n (2 ≤ n ≤ 50000).

Вихідні дані

Одне ціле число, взяте по модулю 10^6, – кількість цілочисельних послідовностей довжини n з невід'ємними членами, які у результаті вищеописаної процедури дають число k.

Приклади