Məsələlər
Суммирование последовательностей
Суммирование последовательностей
Пусть задана некоторая целочисленная последовательность \{\textbf{a_n}\} длины \textbf{n}, состоящая из неотрицательных чисел. Сформируем из нее последовательность \{\textbf{b_n}\} длины \textbf{n--1} по следующему правилу:
\textbf{b_i = a_i + a_i_\{+1\}}.
Проведя такое преобразование \textbf{n--1} раз, мы получим последовательность длины \textbf{1}, то есть одно число, которое обозначим через \textbf{k}.
Вам требуется решить следующую задачу -- зная число \textbf{k}, определить, сколько целочисленных последовательностей длины \textbf{n} с неотрицательными членами дают число \textbf{k} в результате вышеописанной процедуры.
\InputFile
Два целых числа \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{50000}) и \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50000}).
\OutputFile
Одно целое число, взятое по модулю \textbf{10^6}, -- количество целочисленных последовательностей длины \textbf{n }с неотрицательными членами, которые в результате вышеописанной процедуры дают число \textbf{k}.
Giriş verilənləri #1
3 2
Çıxış verilənləri #1
4