#include <bits/stdc++.h>

#define mod 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

struct mat
{
    long long a=0,b=1,c=1,d=1;

    mat operator *(const mat &obj)
    {
        mat res;
        res.a=a*obj.a+b*obj.c; res.b=a*obj.b+b*obj.d;
        res.c=c*obj.a+d*obj.c; res.d=c*obj.b+d*obj.d;
        return res;
    }
    mat operator %(const long long &obj)
    {
        mat res;
        res.a=a%obj; res.b=b%obj;
        res.c=c%obj; res.d=d%obj;
        return res;
    }
};

mat ridica(mat m, int p)
{
    if(p==1) return m;
    if(p%2==0) return ridica((m*m)%mod,p/2)%mod;
    return ((ridica((m*m)%mod,(p-1)/2)%mod)*m)%mod;
}

mat root;

int main()
{
    int n;
    f>>n;
    if(n<=2){g<<1;return 0;}
    n--;
    g<<ridica(root,n).d;
    return 0;
}