/*
TASK:str
LANG:C
*/
#include<stdio.h>
#include<math.h>
#define MAXN 1024
#define mod 4999999
long long f[MAXN];
int d[MAXN][MAXN];
int df[MAXN][MAXN];
int dd[MAXN]={0,1,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,17,2,19,2,3,2,23,2,5,2,3,2,29,2,31,2,3,2,5,2,37,2,3,2,41,2,43,2,3,2,47,2,7,2,3,2,53,2,5,2,3,2,59,2,61,2,3,2,5,2,67,2,3,2,71,2,73,2,3,2,7,2,79,2,3,2,83,2,5,2,3,2,89,2,7,2,3,2,5,2,97,2,3,2,101,2,103,2,3,2,107,2,109,2,3,2,113,2,5,2,3,2,7,2,11,2,3,2,5,2,127,2,3,2,131,2,7,2,3,2,137,2,139,2,3,2,11,2,5,2,3,2,149,2,151,2,3,2,5,2,157,2,3,2,7,2,163,2,3,2,167,2,13,2,3,2,173,2,5,2,3,2,179,2,181,2,3,2,5,2,11,2,3,2,191,2,193,2,3,2,197,2,199,2,3,2,7,2,5,2,3,2,11,2,211,2,3,2,5,2,7,2,3,2,13,2,223,2,3,2,227,2,229,2,3,2,233,2,5,2,3,2,239,2,241,2,3,2,5,2,13,2,3,2,251,2,11,2,3,2,257,2,7,2,3,2,263,2,5,2,3,2,269,2,271,2,3,2,5,2,277,2,3,2,281,2,283,2,3,2,7,2,17,2,3,2,293,2,5,2,3,2,13,2,7,2,3,2,5,2,307,2,3,2,311,2,313,2,3,2,317,2,11,2,3,2,17,2,5,2,3,2,7,2,331,2,3,2,5,2,337,2,3,2,11,2,7,2,3,2,347,2,349,2,3,2,353,2,5,2,3,2,359,2,19,2,3,2,5,2,367,2,3,2,7,2,373,2,3,2,13,2,379,2,3,2,383,2,5,2,3,2,389,2,17,2,3,2,5,2,397,2,3,2,401,2,13,2,3,2,11,2,409,2,3,2,7,2,5,2,3,2,419,2,421,2,3,2,5,2,7,2,3,2,431,2,433,2,3,2,19,2,439,2,3,2,443,2,5,2,3,2,449,2,11,2,3,2,5,2,457,2,3,2,461,2,463,2,3,2,467,2,7,2,3,2,11,2,5,2,3,2,479,2,13,2,3,2,5,2,487,2,3,2,491,2,17,2,3,2,7,2,499,2,3,2,503,2,5,2,3,2,509,2,7,2,3,2,5,2,11,2,3,2,521,2,523,2,3,2,17,2,23,2,3,2,13,2,5,2,3,2,7,2,541,2,3,2,5,2,547,2,3,2,19,2,7,2,3,2,557,2,13,2,3,2,563,2,5,2,3,2,569,2,571,2,3,2,5,2,577,2,3,2,7,2,11,2,3,2,587,2,19,2,3,2,593,2,5,2,3,2,599,2,601,2,3,2,5,2,607,2,3,2,13,2,613,2,3,2,617,2,619,2,3,2,7,2,5,2,3,2,17,2,631,2,3,2,5,2,7,2,3,2,641,2,643,2,3,2,647,2,11,2,3,2,653,2,5,2,3,2,659,2,661,2,3,2,5,2,23,2,3,2,11,2,673,2,3,2,677,2,7,2,3,2,683,2,5,2,3,2,13,2,691,2,3,2,5,2,17,2,3,2,701,2,19,2,3,2,7,2,709,2,3,2,23,2,5,2,3,2,719,2,7,2,3,2,5,2,727,2,3,2,17,2,733,2,3,2,11,2,739,2,3,2,743,2,5,2,3,2,7,2,751,2,3,2,5,2,757,2,3,2,761,2,7,2,3,2,13,2,769,2,3,2,773,2,5,2,3,2,19,2,11,2,3,2,5,2,787,2,3,2,7,2,13,2,3,2,797,2,17,2,3,2,11,2,5,2,3,2,809,2,811,2,3,2,5,2,19,2,3,2,821,2,823,2,3,2,827,2,829,2,3,2,7,2,5,2,3,2,839,2,29,2,3,2,5,2,7,2,3,2,23,2,853,2,3,2,857,2,859,2,3,2,863,2,5,2,3,2,11,2,13,2,3,2,5,2,877,2,3,2,881,2,883,2,3,2,887,2,7,2,3,2,19,2,5,2,3,2,29,2,17,2,3,2,5,2,907,2,3,2,911,2,11,2,3,2,7,2,919,2,3,2,13,2,5,2,3,2,929,2,7,2,3,2,5,2,937,2,3,2,941,2,23,2,3,2,947,2,13,2,3,2,953,2,5,2,3,2,7,2,31,2,3,2,5,2,967,2,3,2,971,2,7,2,3,2,977,2,11,2,3,2,983,2,5,2,3,2,23,2,991,2,3,2,5,2,997,2,3,2,7,2,17,2,3,2,19,2,1009,2,3,2,1013,2,5,2,3,2,1019,2,1021};
int n;
int maxl;
int tmp[MAXN];
int comb(int t, int k)
{
    int j;
    long long ans=1;
    memset(tmp,0,sizeof(tmp));
    for(j=0;j<=n*n;j++)
    {
        tmp[j]=df[t][j]-df[t-k][j]-df[k][j];
    }
    for(j=0;j<=n*n;j++)
    {
        ans=(ans*((int)pow(j,tmp[j])%mod))%mod;
    }
    return ans;
}
void init()
{
    int i,j;
    scanf("%d",&n);
    d[1][1]=1;
    d[2][2]=1;
    for(i=3;i<=n*n;i++)
    {
        if(dd[i]!=i)
            for(j=1;j<n*n;j++)
                d[i][j]=d[dd[i]][j]+d[i/dd[i]][j];
        else
            d[i][i]=1;
    }
    df[1][1]=1;
    for(i=1;i<=n*n;i++)
        for(j=2;j<=n*n;j++)
        {
            tmp[j]+=d[i][j];
            df[i][j]=tmp[j];
        }
}
void solve()
{
    int i,j;
    long long ans=0;
    int pp;
    long long t;
    int  hhh;
    maxl=comb(n,2);
    for(i=n-1;i<=maxl;i++)
    {
        ans=(ans+comb(maxl,i))%mod;
    }
    printf("%lld\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}
