Трипростые числа
(Время: 1 сек. Память: 16 Мб Сложность: 40%)
Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют трехзначное простое число.
Требуется найти количество N-значных трипростых чисел.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N (3 ≤ N ≤ 10000).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать количество N-значных трипростых чисел, которое следует вывести по модулю 109+9.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4 | 204 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|