题目描述

给定一个位数为 $n$ 的正整数 $m$, 若 $m$ 的任意 $3$ 个连续数位组成的整数均为素数, 则称 $m$ 为一个 $n$ 位三连素数. 现给定位数 $n$, 求所有 $n$ 位三连素数的个数 $p$.

输入输出格式

输入 $1$ 行 $1$ 个整数 $n$.

输出 $1$ 行 $1$ 个整数 $p$, 代表所有 $n$ 位三连素数的个数. 由于结果可能很大, 你只需要输出答案对 $1000000009$ 取余的结果.

输入输出样例

输入

6

输出

879

其中, $101131$ 是最小的 $6$ 位三连素数, 其任意 $3$ 个连续数位组成的整数 $101$、$11$、$113$、$131$ 均为质数. 这样的 $6$ 位三连素数共有 $879$ 个, 故输出 $879$.

数据范围

对于 $40\%$ 的测试点, $3\leq n\leq10$.

对于 $80\%$ 的测试点, $3\leq n\leq10^5$.

对于 $100\%$ 的测试点, $3\leq n\leq10^{18}$.