题意 ： 定义Threeprime为它的任意连续3位上的数字，都构成一个3位的质数。 求对于一个n位数，存在多少个Threeprime数。
思路 ： 记录[100, 999]范围内所有素数（标记的是该素数的每一位x1,x2,x3）。然后从n = 4往后，定义dp[i][x2][x3], i 表示到第 i 位时，第 i-1 位为 x2 , 第 i 位x3，此时所包含的情况数。
dp[i][x2][x3] = dp[i][x2][x3] + dp[i-1][x1][x2]；最后求和sum(dp[n][x2][x3]);
//
#include <cstdio>
#include <cstring>
#include <iostream>
#define MOD 1000000009
#define LL long long
using namespace std ; int dp[][][],prime[][][] ;
int vis[] = {} ,cnt = ; void solve()
{
cnt = ;
memset(vis,,sizeof(vis)) ;
for(int i = ; i <= ; i++)
{
if(!vis[i])
{
for(int j = i*i ; j <= ; j += i)
vis[j] = ;
}
}
for(int i = ; i <= ; i ++)
{
if(!vis[i])
{
int x1 = i / ;
int x2 = i / % ;
int x3 = i % ;
prime[x1][x2][x3] = ;
dp[][x2][x3] += ;
cnt ++ ;
}
}
}
int main()
{
int n ;
scanf("%d",&n);
solve() ;
if(n == ) {
printf("%d\n",cnt % MOD) ;
return ;
}
for(int i = ; i <= n ; i++)
for(int x1 = ; x1 <= ; x1 ++)
for(int x2 = ; x2 <= ; x2 ++)
for(int x3 = ; x3 <= ; x3 ++)
if(dp[i-][x1][x2] && prime[x1][x2][x3])
dp[i][x2][x3] = (dp[i][x2][x3] + dp[i-][x1][x2]) % MOD;
int ans = ;
for(int x2 = ; x2 <= ; x2 ++)
{
for(int x3 = ; x3 <= ; x3 ++)
{
ans = (ans+dp[n][x2][x3])%MOD ;
}
}
printf("%d\n",ans) ;
return ;
}