#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long i,j,n;
long x11,x21,x12,x22,a[31][3][3],k;
long mat[3][3];
void powlg(int p)
{
    while(p>1)
    {
        if(p%2==0)
        {
            x11=mat[1][1]*mat[1][1]+mat[1][2]*mat[2][1];
            x12=mat[1][1]*mat[1][2]+mat[1][2]*mat[2][2];
            x21=mat[2][1]*mat[1][1]+mat[2][2]*mat[2][1];
            x22=mat[2][1]*mat[1][2]+mat[2][2]*mat[2][2];
            mat[1][1]=x11%666013;
            mat[1][2]=x12%666013;
            mat[2][1]=x21%666013;
            mat[2][2]=x22%666013;
            p/=2;
        }
        else
        {
            a[++k][1][1]=mat[1][1];
            a[k][1][2]=mat[1][2];
            a[k][2][1]=mat[2][1];
            a[k][2][2]=mat[2][2];
            p--;
        }
    }
    for(i=1;i<=k;i++)
    {
        x11=mat[1][1]*a[i][1][1]+mat[1][2]*a[i][2][1];
        x12=mat[1][1]*a[i][1][2]+mat[1][2]*a[i][2][2];
        x21=mat[2][1]*a[i][1][1]+mat[2][2]*a[i][2][1];
        x22=mat[2][1]*a[i][1][2]+mat[2][2]*a[i][2][2];
        mat[1][1]=x11%666013;
        mat[1][2]=x12%666013;
        mat[2][1]=x21%666013;
        mat[2][2]=x22%666013;
    }
}
int main()
{
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;
    f>>n;
    powlg(n-2);
    g<<(mat[2][2]+mat[1][2])%666013<<'\n';
    return 0;
}