#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
struct matrice
{
    long long a[3][3];
    matrice operator*(const matrice &m)
    {
        matrice matrix;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                matrix.a[i][j]=((this->a[i][1]*m.a[1][j])%MOD+(this->a[i][2]*m.a[2][j])%MOD)%MOD;
        return matrix;
    }
};

matrice power(matrice m,long long k)
{
    if(k==1)
        return m;
    if(k%2==0)
        return power(m*m,k/2);
    else return m*power(m*m,k/2);
}

int main()
{
    int k;
    matrice m;
    m.a[1][1]=0;
    m.a[1][2]=1;
    m.a[2][1]=1;
    m.a[2][2]=1;
    fin>>k;
    m=power(m,k-2);
    fout<<(m.a[1][2]+m.a[2][2])%MOD;
    return 0;
}