#include <fstream>
#define mod 666013
using namespace std;

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

void scan(long &n)
{
    in>>n;
}

void init(long a[][3])
{
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=0;
}

void setzero(long a[][3])
{
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            a[i][j]=0;
}

void mult(long a[][3],long b[][3],long c[][3])
{
    setzero(a);
    for (int k=1;k<=2;k++)
        for (int i=1;i<=2;i++)
            for (int j=1;j<=2;j++)
            {
                a[i][j]=((long long)a[i][j]+((long long)b[i][k]*c[k][j])%mod)%mod;
            }
}

void putere(long a[][3],long n)
{
    long m[3][3];
    long u[3][3];
    if (n==1)
    {
        init(a);
        return;
    }
    if (n%2==0)
    {
        putere(m,n/2);
        mult(a,m,m);
    }
    else
    {
        putere(m,n-1);
        init(u);
        mult(a,m,u);
    }
}

int main()
{
    long a[3][3],n;
    scan(n);
    init(a);
    putere(a,n);
    out<<a[2][1];
    return 0;
}