#include <fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

int rez[3][3], mat[3][3],n, a[3][3];

void ina()
{
    a[1][1]=0;
    a[1][2]=a[2][2]=a[2][1]=1;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            mat[i][j]=a[i][j];
}

void lgput(int p,int mat[3][3])
{
    if(p==0)
    {
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                mat[i][j]=(i==j);
        return;
    }
    if(p%2==0)
    {
        lgput(p/2, mat);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
            {
                rez[i][j] = 0;
                for(int k=1;k<=2;k++)
                {
                    rez[i][j]+=((1LL*mat[i][k]*mat[k][j])%666013);
                }
            }
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                mat[i][j]=rez[i][j];
    }
    else
    {
        lgput(p-1,mat);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
            {
                rez[i][j] = 0;
                for(int k=1;k<=2;k++)
                {
                    rez[i][j]+=((1LL*mat[i][k]*a[k][j])%666013);
                }
            }
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                mat[i][j]=rez[i][j];
    }
}

int main()
{
    cin>>n;

    ina();

    lgput(n, mat);

    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            rez[i][j]=0;

    int fib[3][3];
    fib[1][1]=0;
    fib[1][2]=1;

    for(int i=1;i<=1;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
            {
                rez[i][j]+=((1LL*fib[i][k]*mat[k][j])%666013);
            }
    cout<<rez[1][1];
    return 0;
}