//IN THE NAME OF GOD

#include <bits/stdc++.h>
using namespace std;
int del=10739;
vector < int  >v;
vector <string> s;
bool prime[100000];
string binary(int a){
    string ret="";
    while(a){
        ret.push_back(a%2+'0');
        a/=2;
    }
    for(int i=0;i<ret.size()/2;i++)
        swap(ret[i],ret[ret.size()-1-i]);
    return ret;
}
int dis(string a,string b){
    for(int i=0;i<min(a.size(),b.size());i++){
        if(a[i]!=b[i]){
            return b.size()-i+a.size()-i;
        }
    }
    return abs(b.size()-a.size());
}
int main(){
    for(int i=2;i<=10739;i++){
        if(!prime[i]){
            for(int j=i*i;j<100000;j+=i)
                prime[j]=1;
            v.push_back(i);
            s.push_back(binary(i));
        }
    }
    int ans=1;
    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            if(!prime[v[i]+v[j]+1]){
                ans*=dis(s[i],s[j]);
            }
            ans%=del;
        }
    }
    cout<<ans<<endl;
    return 0;
}