#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct Mat
{
    long long int mat[2][2];
};
Mat nullMat={{{1,0},{0,1}}};
int k;
Mat initMat={{{1,1},{1,0}}};
Mat prod(Mat a,Mat b)
{
    Mat ret;
    ret.mat[0][0]=(a.mat[0][0]*b.mat[0][0]+a.mat[0][1]*b.mat[1][0])%mod;
    ret.mat[0][1]=(a.mat[0][0]*b.mat[0][1]+a.mat[0][1]*b.mat[1][1])%mod;
    ret.mat[1][0]=(a.mat[1][0]*b.mat[0][0]+a.mat[1][1]*b.mat[1][0])%mod;
    ret.mat[1][1]=(a.mat[1][0]*b.mat[0][1]+a.mat[1][1]*b.mat[1][1])%mod;
    return ret;
}
Mat pow(Mat mat,int n)
{
    if(!n)
        return nullMat;
    if(n&1)
        return prod(mat,pow(prod(mat,mat),n>>1));
    return pow(prod(mat,mat),n>>1);
}
int main()
{
    fin>>k;
    fout<<pow(initMat,k).mat[0][1]<<'\n';
    return 0;
}