#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream g("kfib.out");
long long int a[2][2],sol[2][2],rez[2][2],f[2][2];
long long int inmultire(long int k,long int x[2][2])
{
    if(k>0)
    {
        if(k%2==0)
        {
            rez[0][0]=((a[0][0]*sol[0][0])%666013+(a[0][1]*sol[1][0])%666013)%666013;
            rez[0][1]=((a[0][0]*sol[0][1])%666013+(a[0][1]*sol[1][1])%666013)%666013;
            rez[1][0]=((a[1][0]*sol[0][0])%666013+(a[1][1]*sol[1][0])%666013)%666013;
            rez[1][1]=((a[1][0]*sol[0][1])%666013+(a[1][1]*sol[1][1])%666013)%666013;
            a[0][0]=sol[0][0]=rez[0][0];
            a[0][1]=sol[0][1]=rez[0][1];
            a[1][1]=sol[1][1]=rez[1][1];
            a[1][0]=sol[1][0]=rez[1][0];
            inmultire(k/2,x);
        }
        else
        {
            long long int a1,b,c,d;
            a1=((x[0][0]*sol[0][0])%666013+(x[0][1]*sol[1][0])%666013)%666013;
            b=((x[0][0]*sol[0][1])%666013+(x[0][1]*sol[1][1])%666013)%666013;
            c=((x[1][0]*sol[0][0])%666013+(x[1][1]*sol[1][0])%666013)%666013;
            d=((x[1][0]*sol[0][1])%666013+(x[1][1]*sol[1][1])%666013)%666013;

            x[0][0]=a1;
            x[0][1]=b;
            x[1][1]=d;
            x[1][0]=c;
            inmultire(k-1,x);
        }
    }
    else
        return x[0][0]%666013;
}
int main()
{
    long long int k;
    fin>>k;
    fin.close();
    k--;
    a[0][0]=a[0][1]=a[1][0]=1;
    a[1][1]=0;
    sol[0][0]=sol[0][1]=sol[1][0]=1;
    sol[1][1]=0;
    f[0][0]=f[0][1]=f[1][0]=1;
    f[1][1]=0;
    long int x[2][2];
    x[0][0]=x[1][1]=1;x[1][0]=0;
    x[0][1]=0;
    g<<inmultire(k,x);
}