Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт У Олеси имеется n кубиков. Она хочет использовать их для строительства красивых башен. Красивойбашнейназываетсяконструкцияизкубиков, состоящаяизнекоторогоколичествауровней. Самый высокий уровень состоит из единственного кубика, второй сверху — из двух кубиков, третий – из трёх, и так далее — нижний уровень содержит количество кубиков, равное количеству уровней в башне. Олесяхочетиспользоватьвсекубикидлястроительстванекоторогоколичествакрасивыхбашен. Ваша задача — написать программу, которая определит количество способов построить красивые башни, использовав все n имеющихся кубиков. Так как это количество может быть очень большим, требуется вывести остаток от деления этого количества на 1000000007 (109 + 7). Два способа считаются различными, если в них построено разное количество красивых башен или количество башен хотя бы одной высоты в них различается. Формат входных данных Единственная строка входных данных содержит единственное целое число n — количество имеющихся у Олеси кубиков (1 ⩽ n ⩽ 105). Формат выходных данных Единственная строка выходных данных должна содержать единственное целое число — остаток от деления искомого количества способов на 1000000007 (109 + 7). Система оценки Решения, работающие только при 1 ⩽ n ⩽ 50 будут оцениваться из 50 баллов. Пример стандартный ввод стандартный вывод 7 4 Замечание Для семи кубиков возможны следующие четыре варианта:
1. Семь башен высоты 1. 2. Четыре башни высоты 1, одна башня высоты 2. 3. Одна башня высоты 1, две башни высоты 2. 4. Одна башня высоты 1, одна башня высоты 3.
1. Семь башен высоты 1. 2. Четыре башни высоты 1, одна башня высоты 2. 3. Одна башня высоты 1, две башни высоты 2. 4. Одна башня высоты 1, одна башня высоты 3.