Background

A practice problem from Jiaochuan Shuyuan.

Problem Description

If every consecutive three-digit segment of a number is a prime greater than $100$, then the number is called a three-prime number. For example, $113797$ is a $6$-digit three-prime number, because $113$, $137$, $379$, $797$ are all prime.

Input Format

An integer $n$ ($3 \le n \le {10}^4$), denoting the number of digits of a three-prime number.

Output Format

A single integer, the number of $n$-digit three-prime numbers.

Because this number can be large, output the remainder of the answer modulo ${10}^9+9$.

4

204

Hint

Translated by ChatGPT 5