P2359 Three-Prime Number

A practice problem from Jiaochuan Shuyuan.

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.

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

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$.

Translated by ChatGPT 5