该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

蛟川书院的一道练习题

题目描述

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

输入格式

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

输出格式

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

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

4

204