Description

如果一个数的所有连续三位数字都是大于 $100$ 的素数，则该数称为三素数数。比如 $113797$ 是一个 $6$ 位的三素数数，因为 $113$、$137$、$379$、$797$ 都是素数。

Input Format

一个整数 $n$（$3 \le n \le {10}^4$），表示三素数数的位数。

Output Format

一个整数，表示 $n$ 位三素数的个数。

由于这个数可能很大，你需要输出答案除以 ${10}^9+9$ 的余数。

4

204