#include <iostream>
#include <fstream>
#define mod 666013
std::ifstream in("kfib.in");
std::ofstream out("kfib.out");

using namespace std;

int n;
int mat[3][3],sol[3][3];

void mult(int A[][3],int B[][3],int C[][3])
{
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                C[i][j]=(C[i][j] + 1LL * A[i][k] * B[k][j])%mod;
}

void lgp(int p, int m[][3])
{
    int c[3][3],aux[3][3],i;
    c[0][0]=0;
    c[1][0]=1;
    c[0][1]=1;
    c[1][1]=1;
    m[0][0]=1;
    m[1][1]=1;
    for(int i=0; (1<<i)<=p; i++)
    {
        if(p & (1<<i))
        {
            aux[0][0]=0;
            aux[1][0]=0;
            aux[0][1]=0;
            aux[1][1]=0;
            mult(m,c,aux);
            m[0][0]=aux[0][0];
            m[1][0]=aux[1][0];
            m[0][1]=aux[0][1];
            m[1][1]=aux[1][1];
        }
        aux[0][0]=0;
        aux[1][0]=0;
        aux[0][1]=0;
        aux[1][1]=0;
        mult(c,c,aux);
        c[0][0]=aux[0][0];
        c[1][0]=aux[1][0];
        c[0][1]=aux[0][1];
        c[1][1]=aux[1][1];
    }

}
int main()
{
    in>>n;
    mat[0][0]=0;
    mat[1][0]=1;
    mat[0][1]=1;
    mat[1][1]=1;
    lgp(n-1,sol);
    out<<sol[1][1];
    return 0;
}