//https://infoarena.ro/problema/kfib
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long result[2][1];
long long M[2][2];
#define Nmax  666013
long long 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];
}
long long inmultire2(long long rez[2][1],long long A[2][2])
{
    long long C[2][1];
    int j=0,i,k;
    C[0][0]=C[0][1]=0;
    for( i = 0; i <=1; i++)
    {
        for(k = 0; k <= 1; k++)
            C[i][j]=( C[i][j]+ 1LL * A[i][k] * rez[k][j])%Nmax;
    }

    for(i = 0; i <= 1; i++)
        rez[i][j] = C[i][j];
}
int main(void)
{
    result[1][0]=1;
    M[0][0]=1;
    M[0][1]=1;
    M[1][0]=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;
}