Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Стаканы

(Время: 1 сек. Память: 16 Мб Сложность: 40%)

Как известно, стакан – предмет весьма функциональный. Самый банальный способ применения – ёмкость для жидкости, самый оригинальный ещё не изобретён. А мальчик Слава строит из стаканов башни, пользуясь удивительным свойством стаканов ставиться друг на друга или вставляться друг в друга.

Слава строит башни из стаканов высотой 10 сантиметров, которых у него имеется бесконечное количество. Стакан можно поставить на уже имеющуюся конструкцию либо дном вниз, либо дном вверх. Если предыдущий стакан установлен аналогично новому, то конструкция вырастет на 1 сантиметр, так как стаканы надеваются друг на друга. В противном случае башня вырастет на 10 сантиметров.

Однажды Слава заметил, что ни в коем случае нельзя вставлять друг в друга более трёх стаканов, иначе один из стаканов обязательно разобьётся.

На рисунке показан пример башни высотой 32 сантиметра из 5 стаканов.

Слава умудрился построить красивую башню высотой k сантиметров. Но когда он пошёл за фотоаппаратом, чтобы запечатлеть это достижение, случайно задел конструкцию, и башня упала. Пытаясь восстановить своё творение, Слава понял, что есть несколько способов построить башню аналогичной высоты. Помогите Славе вычислить точное количество способов.

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

Входной файл INPUT.TXT содержит натуральное число k (k ≤ 105).

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

В выходной файл OUTPUT.TXT выведите количество способов построить башню заданной высоты, взятое по модулю 106.

Примеры

INPUT.TXTOUTPUT.TXT
1112
2226
33212

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru