#include<iostream>
#include<vector>
using namespace std;
long long mod = 1000000009;
long long d[10000][10][10];
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    vector<bool> p(1000,true);
    for(int i = 100; i < 1000; i++)
        for(int j = 2; j * j <= i; j++)
            if (i % j == 0)
            {
                p[i] = false;
                break;
            }
    vector<int> pr;
    for(int i = 100; i < 1000; i++)
        if (p[i])
        {
            pr.push_back(i);
            d[3][(i % 100) / 10][i % 10]++;
        }
    for(int i = 4; i <= n; i++)
        for(size_t k = 0; k < pr.size(); k++)
        {
            int j = pr[k];
            d[i][(j % 100) / 10][j % 10] = (d[i][(j % 100) / 10][j % 10] + d[i - 1][j / 100][(j % 100) / 10]) % mod;
        }
    long long ans = 0;
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            ans = (ans + d[n][i][j]) % mod;
    cout<<ans;
     return 0;
}