У маленького мальчика есть набор из N кубиков. Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера (обратите особое внимание на то, что лестница не может иметь две одинаковые ступени). Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика. На рисунке приведены примеры лестниц для N=11 и N=5:
Найдите число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков.
Исходные данные
Результат
Примеры
исходные данные | результат |
---|
5
| 2
|
212
| 995645335
|
Источник задачи: Ural State University Internal Contest '99 #2