#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long int k;
long long int mat1[5][5], mat2[5][5], mat3[5][5];
int main()
{
    f>>k;
    mat1[0][0]=1;
    mat1[0][1]=0;
    mat2[0][0]=1;
    mat2[0][1]=1;
    mat2[1][0]=1;
    mat2[1][1]=0;
    for(int i=0; i<k; i++)
    {
        long long int s=0;
        if(i%2==0)
        {
            for(int j=0; j<2; j++)
                s+=(mat1[0][j]*mat2[j][0])%666013;
            mat3[0][0]=s;
            s=0;
            for(int j=0; j<2; j++)
                s+=(mat1[0][j]*mat2[j][1])%666013;
            mat3[0][1]=s;
        }
        else
        {
            for(int j=0; j<2; j++)
                s+=(mat3[0][j]*mat2[j][0])%666013;
            mat1[0][0]=s;
            s=0;
            for(int j=0; j<2; j++)
                s+=(mat3[0][j]*mat2[j][1])%666013;
            mat1[0][1]=s;
        }
    }
    if(k%2==0)
        g<<mat1[0][1];
    else
        g<<mat3[0][1];
    return 0;
}