Красивые последовательности

Математики – люди, весьма ценящие красоту. Они умеют находить ее даже в объектах, к которым, по мнению большинства, это понятие даже не может быть применимо. Например, недавно один математик, занимавшийся изучением последовательностей натуральных чисел, заметил, что некоторые из последовательностей отличаются необычайной красотой. Особенно красивыми он посчитал последовательности a₁, ... , a_n длины n из чисел от 1 до k, обладающие следующими свойствами:

• a₁=1;
• если a_i=M , i > 1, то найдется j < i : a_j=M-1, либо M=1.

Примером такой последовательности для n = 5, k = 3 является «1, 1, 2, 3, 1», а последовательность «1, 3, 1, 4» не является особенно красивой ни для каких n и k.

Ваша задача состоит в нахождении числа особенно красивых последовательностей для заданных n и k.

Входные данные

Входной файл INPUT.TXT содержит два целых числа: n и k (1 ≤ n, k ≤ 500).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]