eolymp
bolt
Try our new interface for solving problems
Məsələlər

Суммирование последовательностей

Суммирование последовательностей

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Пусть задана некоторая целочисленная последовательность {a_n} длины n, состоящая из неотрицательных чисел. Сформируем из нее последовательность {b_n} длины n–1 по следующему правилу:

b_i = a_i + a_i_{+1}.

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

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

Giriş verilənləri

Два целых числа k (0k50000) и n (2n50000).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3 2
Çıxış verilənləri #1
4
Mənbə ACM ICPC 2012-2013 NEERC Siberian Group