//IN THE NAME OF GOD

#include <bits/stdc++.h>
using namespace std;
int del=10739,ans[10],javab;
vector < int  >v,t,d;
bool prime[100000];
int tah(int a){
    while(a%10!=a)
        a/=10;
    return a;
}
int tool(int a){
    int ret=0;
    while(a){
        ret++;
        a/=10;
    }
    return ret;
}
int main(){
    for(int i=2;i<10739;i++){
        if(!prime[i]){
            for(int j=i*i;j<10739;j+=i)
                prime[j]=1;
            if(i>7){
                v.push_back(i%10);
                t.push_back(tah(i));
                d.push_back(tool(i)-1);
            }
        }
    }
    for(int i=0;i<v.size();i++){
        ans[v[i]]=max(ans[t[i]]+d[i],ans[v[i]]);
    }
    for(int i=0;i<10;i++){
        javab=max(javab,ans[i]+1);
    }
    cout<<(javab*javab*javab)%del<<endl;
    return 0;
}