#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void inmultire(int mat1[2][2], int mat2[2][2])
{
    int r[2][2]= {0};
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                r[i][j]=(r[i][j]+1LL*mat1[i][k]%mod*mat2[k][j]%mod)%mod;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            mat2[i][j]=r[i][j];
}
void put(int mat[2][2], int exp)
{
    int r[2][2]= {{1,0},{0,1}};
    while(exp)
    {
        if(exp%2==1)
            inmultire(mat,r);
        inmultire(mat,mat);
        exp/=2;
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            mat[i][j]=r[i][j];
}
int n,mat[2][2]= {{1,1},{1,0}},fibo[2][2]= {{1,0},{0,0}};
int main()
{
    fin>>n;
    if(n<=1)
    {
        fout<<n;
        return 0;
    }
    put(mat,n-1);
    inmultire(mat,fibo);
    fout<<fibo[0][0]%mod;
    return 0;
}