#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

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

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

void inmultire(long long c[2][2], long long a[2][2], long long b[2][2])
{
    for(int i=0; i<=1; i++)
    {
        for(int j=0; j<=1; j++)
        {
            c[i][j]=0;
            for(int k=0; k<=1; k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
                c[i][j]%=MOD;
            }
        }
    }
}

long long n, c[2][2];
long long a[2][2]={1, 1, 1, 0};
long long i[2][2]={1, 0, 0, 1};
int main()
{
    fin>>n;
    if(n<=2)
    {
        fout<<1;
        return 0;
    }
    n-=2;
    while(n!=0)
    {
        if(n%2!=0)
        {
            inmultire(c, i, a);
            copiere(i, c);
        }
        inmultire(c, a, a);
        copiere(a, c);
        n/=2;
    }
    fout<<(i[0][0]+i[0][1])%MOD;
    return 0;
}