/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=8*12345;
bool isP[maxn];
int n;
const int MOD=1000000007;
LL ai[2][maxn];
LL sum[maxn];
int bi[maxn];
int E;
void init()
{
    memset(isP,0,sizeof(isP));
    isP[1]=1;
    for(int i=2; i<=80000; i++)
    {
        if(isP[i])continue;
        for(int j=i+i; j<=80000; j+=i)
        {
            isP[j]=1;
        }
    }

    E=0;
    for(int i=1; i<=80000; i++)
    {
        if(isP[i])
        {
            isP[i]=0;
            continue;
        }
        isP[i]=1;
        E++;
        bi[E]=i;
    }

    memset(ai,0,sizeof(ai));
    for(int i=1; i<=E; i++)
    {
        for(int j=i; j<=E; j++)
        {
            LL t1=bi[i];
            LL t2=bi[j];

            if(t1+t2<=80000)
            {
                ai[0][t1+t2]=(ai[0][t1+t2]+1);
            }
            if(t1*t2<=80000)
            {
                ai[1][t1*t2]=(ai[1][t1*t2]+1);
            }
        }
    }
}
int k;
void play()
{
    sum[k]=0;
    sum[k]+=isP[k];
    LL p=(ai[0][k]+ai[1][k]);
    sum[k]=(sum[k]+p)%MOD;
    LL n1=0;
    LL n2=0;
    for(int i=1; i<=E; i++)
    {
        if(bi[i]>=k)break;
        int t=k-bi[i];
        if(t%2==0)
        {
            int q=t/2;
            if(q==bi[i])
            {
                n1+=2;
            }
            else n1+=isP[q];
        }
        n1=(n1+ai[0][t]);
        n2=(n2+ai[1][t]);
        int q=k%bi[i];
        if(q==0)
        {
            t=k/bi[i];
            int q=sqrt(t);
            if(q*q==t)
            {
                if(q==bi[i])
                {
                    n1+=2;
                }
                else n1+=isP[q];
            }
            n1=(n1+ai[1][t]);
        }
    }
    n1=n1/3;
    sum[k]=(sum[k]+n1);
    sum[k]=(sum[k]+n2);
    printf("%lld\n",sum[k]);
}
int main()
{
    init();
    while(scanf("%d",&k)!=EOF)
    {
        play();
    }
    return 0;
}