#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
const ll mod=666013;
ll N;

struct matrix
{
    ll elem[3][3];
    matrix()
    {
        elem[1][1]=elem[2][2]=1;
        elem[1][2]=elem[2][1]=0;
    }
};

matrix V;

matrix produs(matrix A,matrix B)
{
    matrix C;
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    {
        ll ans=0;
        for(int k=1;k<=2;k++)
        {
            ans=(ans+((A.elem[i][k]%mod)*(B.elem[k][j]%mod))%mod)%mod;
            if(ans<0)ans+=mod;
        }
        C.elem[i][j]=ans;
    }
    return C;
}

matrix Exp(matrix B,ll exp)
{
    matrix A;
    while(exp)
    {
        if(exp&1) A=produs(A,B);
        exp>>=1;
        B=produs(B,B);
    }
    return A;
}

ll Compute(ll n)
{
    if(n==0) return 0;
    else
    {
        matrix C=Exp(V,n);
        return C.elem[2][1];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    V.elem[1][1]=V.elem[1][2]=V.elem[2][1]=1;
    V.elem[2][2]=0;
    f>>N;
    g<<Compute(N);

    return 0;
}