//https://infoarena.ro/problema/kfib
#include <fstream>
#define Nmax  666013
using namespace std;

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

long long result[1][2];
long long M[2][2];

void inmultire(long long A[2][2],long long B[2][2])
{

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

    for( i = 0; i <= 1 ; i++)
        for( j = 0; j <= 1; j++)
            A[i][j] = C[i][j];
}

void inmultire2(long long rez[1][2],long long A[2][2])
{
    long long C[1][2];
    int i=0,j,k;
    for( j = 0; j <=1; j++)
    {
        C[i][j]=0;
        for(k = 0; k <= 1; k++)
            C[i][j]=( C[i][j]+ 1LL * rez[i][k] * A[k][j])%Nmax;
    }
    i=0;
    for(j = 0; j<= 1; j++)
        rez[i][j] = C[i][j];
}

int main(void)
{
    result[0][1]=1;
    M[0][1]=1;
    M[1][0]=1;
    M[1][1]=1;
    long long p;
    fin>>p;
    while(p)
    {
        if(p%2==1)
            inmultire2(result,M);
        inmultire(M,M);
        p=p/2;
    }
    fout<<result[0][0];
    return 0;
}