Стаканы
(Время: 1 сек. Память: 16 Мб Сложность: 40%)
Как известно, стакан – предмет весьма функциональный. Самый банальный способ применения – ёмкость для жидкости, самый оригинальный ещё не изобретён. А мальчик Слава строит из стаканов башни, пользуясь удивительным свойством стаканов ставиться друг на друга или вставляться друг в друга.
Слава строит башни из стаканов высотой 10 сантиметров, которых у него имеется бесконечное количество. Стакан можно поставить на уже имеющуюся конструкцию либо дном вниз, либо дном вверх. Если предыдущий стакан установлен аналогично новому, то конструкция вырастет на 1 сантиметр, так как стаканы надеваются друг на друга. В противном случае башня вырастет на 10 сантиметров.
Однажды Слава заметил, что ни в коем случае нельзя вставлять друг в друга более трёх стаканов, иначе один из стаканов обязательно разобьётся.
На рисунке показан пример башни высотой 32 сантиметра из 5 стаканов.
Слава умудрился построить красивую башню высотой k сантиметров. Но когда он пошёл за фотоаппаратом, чтобы запечатлеть это достижение, случайно задел конструкцию, и башня упала. Пытаясь восстановить своё творение, Слава понял, что есть несколько способов построить башню аналогичной высоты. Помогите Славе вычислить точное количество способов.
Входные данные
Входной файл INPUT.TXT содержит натуральное число k (k ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите количество способов построить башню заданной высоты, взятое по модулю 106.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 11 | 2 |
| 2 | 22 | 6 |
| 3 | 32 | 12 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
