#include <bits/stdc++.h>
#define M 666013;
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
struct Mat
{
    int mat[2][2];
};
const Mat nullMat=
{
    {{1, 0},
     {0, 1}}
};
const Mat initMat=
{
    {{1, 1},
     {1, 0}}
};

Mat prod(Mat a,Mat b)
{
    Mat ret;
    ret.mat[0][0]=(1LL*a.mat[0][0]*b.mat[0][0]+1LL*a.mat[0][1]*b.mat[1][0])%M;
    ret.mat[0][1]=(1LL*a.mat[0][0]*b.mat[0][1]+1LL*a.mat[0][1]*b.mat[1][1])%M;
    ret.mat[1][0]=(1LL*a.mat[1][0]*b.mat[0][0]+1LL*a.mat[1][1]*b.mat[1][0])%M;
    ret.mat[1][1]=(1LL*a.mat[1][0]*b.mat[0][1]+1LL*a.mat[1][1]*b.mat[1][1])%M;
    return ret;
}

Mat pwr(Mat mat,int n)
{
    if(!n) return nullMat;
    if(n&1) return prod(mat,pwr(prod(mat,mat),n>>1));
    return pwr(prod(mat,mat),n>>1);
}

int main()
{
    int n;
    f>>n;
    g<<pwr(initMat,n).mat[0][1]<<'\n';
    f.close();
    g.close();
    return 0;
}