Построение лестницы
Имея
n кирпичиков, вы хотите выстроить из них лестницу, укладывая кирпичики один на другой в соседние столбцы. Поскольку это лестница, никакие два столбца не должны быть одинаковой высоты. Правые столбцы всегда должны быть выше левых. Зная n кирпичиков, хочется понять, сколькими способами можно построить такую корректную лестницу.Входные данные
Во входных данных задано одно целое число
n (5 ≤ n ≤ 500).Выходные данные
Программа должна вывести количество различных лестниц, которые можно получить из этих кирпичиков.
Примеры
Вход | Выход |
5 | 2 |
11 | 11 |
212 | 995645335 |
Пояснение
- n = 5
ㅤ | x |
x | x |
x | x |
ㅤ | x |
ㅤ | x |
ㅤ | x |
x | x |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB