Задача O. Меч-кладенец ≡

Условие

...

Сколько девичьих в воду упало колец,

Сколько бед натерпелось от Лиха-злодея!

Но вступился за правду удал-молодец.

И срубил в душном логове меч-кладенец

Семь голов у проклятого Змея.

...

Всеволод Рождественский, "Русская сказка", 1962 г.

Всякий, кто брал в руки меч-кладенец, знает, что оружие это заклятое, а значит коварное. То подарок от любимой девушки заставит в воду выбросить, то вдруг атакует лучшего друга, а то на нового владельца проклятье нашлёт. А чтобы снять заклятие, нужно особый обряд совершить или условие выполнить.

Меч, доставшийся Всеволоду, требовал, чтобы в бою со Змеем богатырь первым ударом срубил чудищу любое натуральное число голов, а каждым следующим — на 1 или 2 больше, чем предыдущим. Определите количество способов победить n-голового Горыныча, нанеся ровно k ударов.

Формат входных данных

Две строки входных данных содержат два натуральных числа: n и k.

Формат выходных данных

Выведите одно натуральное число — количество различных подходящих последовательностей ударов. Гарантируется, что хотя бы одна подходящая последовательность есть.

Ограничения

3 ≤ n ≤ 1000

2 ≤ k ≤ 20

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 30 баллов.

Решения, верно работающие при k = 2, получат не менее 20 баллов.

Пояснение к примерам

В первом примере существует единственная подходящая последовательность, позволяющая одолеть семиголового Змея за три удара: 1, 2, 4.

Во втором примере существует две подходящие последовательности: 1, 2, 4, 6 и 1, 3, 4, 5.

Примеры тестов

7
3

1

13
4

2