Суммирование последовательностей
Пусть задана некоторая целочисленная последовательность {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.