ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1586. Трипростые числа

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Отдых на море — это замечательно! Но вот программисту Паше ужасно скучно лежать на пляже в Турции. Настолько скучно, что Паша решил посчитать количество трехзначных простых чисел. Он так увлекся этим занятием, что начал изучать 3-простые числа. Так Паша называет числа, у которых любые 3 подряд идущие цифры образуют трехзначное простое число. Паша уже начал работу над теорией божественного происхождения таких чисел, когда какие-то хулиганы окатили Пашу холодной водой и стали кричать какие-то загадочные слова вроде «Sunstroke!», «Sonnenstich!» и «Colpo di sole!»
Вам предстоит продолжить дело Паши и выяснить насколько часты (или редки) 3-простые числа.

Исходные данные

Ввод содержит целое число n (3 ≤ n ≤ 10000).

Результат

Выведите количество n-значных 3-простых чисел, вычисленное по модулю 109 + 9.

Пример

исходные данныерезультат
4
204
Автор задачи: Денис Мусин
Источник задачи: ACM ICPC 2007–2008. NEERC. Восточный подрегион. Екатеринбург, 27 октября 2007 г.