#include <fstream>
using namespace std;
struct F
{
    long long mat[3][3];
};
F PROD(F a,F b)
{
    F c;
    c.mat[1][1]=0;
    c.mat[1][2]=0;
    c.mat[2][1]=0;
    c.mat[2][2]=0;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%666013;
    return c;
}
F exp(F a,int b)
{
    F p;
    p.mat[1][1]=1;
    p.mat[1][2]=0;
    p.mat[2][1]=0;
    p.mat[2][2]=1;
    while(b>0)
    {
        if(b&1)
        {
            p=PROD(p,a);
        }
        a=PROD(a,a);
        b/=2;
    }
    return p;
}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int n;
    cin>>n;
    n--;
    F A,B;
    A.mat[1][1]=1;
    A.mat[1][2]=1;
    A.mat[2][1]=0;
    A.mat[2][2]=1;

    B.mat[1][1]=0;
    B.mat[1][2]=1;
    B.mat[2][1]=1;
    B.mat[2][2]=1;
    F FU=exp(B,n);
    B=PROD(A,FU);
    cout<<B.mat[2][2];
    return 0;
}