#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long

using namespace std;
#define cin in
#define cout out
ifstream in ("kfib.in");
ofstream out ("kfib.out");

int k;
#define mod 666013
struct matrix {int mat[2][2]; int n; int m;};
matrix I;

matrix multi(matrix X, matrix Y)
{
    matrix ans; ans.n=X.n; ans.m=Y.m;

    for (int i=0; i<X.n; i++)
        for (int j=0; j<Y.m; j++)
        {
            ans.mat[i][j]=0;
            for (int t=0; t<X.m; t++)
            {
                ans.mat[i][j]+=(X.mat[i][t]*Y.mat[t][j])%mod;
                ans.mat[i][j]%=mod;
            }
        }
    return ans;
}

matrix expon(matrix base, int exp)
{
    if (exp==0) return I; if (exp==1) return base;
    matrix aux=expon(base, exp/2);

    return (exp%2==0 ? multi(aux, aux) : multi(multi(aux, aux), base));
}

signed main()
{
    cin>>k;
    matrix A;
    A.mat[0][0]=0; A.mat[0][1]=1; A.mat[1][0]=1; A.mat[1][1]=1; A.n=2; A.m=2;
    matrix B; B.mat[0][0]=1; B.mat[1][0]=1; B.n=2; B.m=1;
    if (k==0) {cout<<1; return 0;}
    if (k==1) {cout<<1; return 0;}

    I.n=2; I.m=2; I.mat[0][0]=1; I.mat[0][1]=0; I.mat[1][0]=0; I.mat[1][1]=1;
    A=expon(A, k-2);
    B=multi(A, B);

    cout<<B.mat[1][0];
    return 0;
}