#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long a[3][3]={{0,0,0},{0,0,1},{0,1,1}},fibo,n;
void copie(long long a[3][3],long long b[3][3])
{
    for (int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            b[i][j]=a[i][j];
}
void inmult(long long a[3][3],long long b[3][3])
{
    long long c[3][3],s;
    for (int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        {
            s=0;
            for (int k=1;k<=2;k++)
                s+=(a[i][k]*b[k][j]);
            c[i][j]=s%666013;
        }
        copie(c,a);
}
void pwm(long long a[3][3],long long p)
{
    long long b[3][3];
    if (p>1)
        if (p%2)
            {
                copie(a,b);
                pwm(b,p-1);
                inmult(a,b);
            }
            else
            {
                pwm(a,p/2);
                copie(a,b);
                inmult(a,b);
            }

}
int main()
{
    fin>>n;
    pwm(a,n-2);
    fibo=a[2][1]+a[2][2];
    fout<<fibo;
    fin.close();
    fout.close();
    return 0;
}