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

Натуральное число называется трипростым, если любые три подряд идущие цифры образуют трёхзначное простое число. Посчитайте количество $N$-значных трипростых чисел по модулю $10^9 + 9$.

В единственной строке — число $N$ ($3 \le N \le 10^4$).

Выведите количество $N$-значных трипростых чисел по модулю $10^9 + 9$.