ЗАДАЧА I
Гирлянда
| Имя входного файла: | lamps.in |
| Имя выходного файла: | lamps.out |
| Ограничение по времени: | 3 секунды |
| Ограничение по памяти: | 64 Мб |
По личному распоряжению Президента республики Беларусь, 31 декабря 2008 года все население республики должно быть готово к встрече Нового 2009 года. Распоряжение это касается всех жителей Беларуси, в том числе и белорусского коллеги нашего Святого Миколая, Дзеда Мароза, также известного как Зюзя.
Зюзя очень любит Новый год и еще больше уважает своего президента, поэтому он решил подготовиться к празднику основательно. Установив на главной площади елку, купив украшений, засыпав всю республику снегом и подарив всем ее жителям новогоднее настроение, наш Дзед Мароз понял, что ему чего не хватает. А не хватало ему гирлянды. Да, да, длинной мигающей гирлянды, состоящей из множества разноцветных лампочек.
К счастью, как раз в канун Нового года отечественный производитель гирлянд – Белорусский Национальный Гирляндо-паятельный завод изготовил опытный образец гирлянды нового поколения и предоставил его Дзеду Морозу для тестирования.
Новая модель гирлянды состоит из опорной планки и N лампочек различных цветов, расположенных в определенном порядке. Каждая лампочка крепится к опорной планке проводом длиной К метров. При этом точки закрепления проводов расположены в ряд с расстоянием 1 метр между соседними. Благодаря такой прогрессивной конструкции, Зюзя может менять порядок следования лампочек в гирлянде, переставляя соседние лампочки, пока это позволяет длина подключенных к ним проводов. Т.е. каждая лампочка может быть перемещена в любую сторону не более чем на К метров от своего начального положения.
Например, для гирлянды, состоящей из 3 лампочек, соединенных проводами в 1 метр, Зюзя может получить 3 возможных расположения лампочек:
Помогите Дзеду Морозу определить, сколькими способами он может расставить лампочки в гирлянде.
Входные данные
В единственной строке входного файла записаны два целых числа N и K (1 ≤ N ≤ 100, 1 ≤ K ≤ 6).
Выходные данные
В выходной файл выведите единственное число – количество способов расставить лампочки в гирлянде.
Пример
| lamps.in | lamps.out |
|---|---|
|
|