#include <iostream>
#include <fstream>
using namespace std;
long long int matFib[3][3];
const int MOD=666013;
ifstream f("kfib.in");
ofstream g("kfib.out");
void Putere(long long int n)
{
    long long int matNou[3][3]={0},copie,copie2;
    ///cout<<n<<'\n';
    ///cout<<matFib[1][1]<<' '<<matFib[1][2]<<'\n'<<matFib[2][1]<<' '<<matFib[2][2]<<'\n'<<'\n';
    if(n==1)
        return;
    if(n%2==1)
    {
        Putere(n-1);
        copie=matFib[1][1],copie2=matFib[1][2];
        matFib[1][1]=(matFib[1][1]+matFib[1][2])%MOD;
        matFib[1][2]=copie;
        matFib[2][1]=copie;
        matFib[2][2]=copie2;
        ///cout<<matFib[1][1]<<' ';
    }
    else
    {
        Putere(n/2);
        matNou[1][1]=(matFib[1][1]*matFib[1][1]+matFib[1][2]*matFib[2][1])%MOD;
        matNou[1][2]=(matFib[1][1]*matFib[1][2]+matFib[1][2]*matFib[2][2])%MOD;
        matNou[2][1]=(matFib[1][1]*matFib[2][1]+matFib[2][1]*matFib[2][2])%MOD;
        matNou[2][2]=(matFib[1][2]*matFib[2][1]+matFib[2][2]*matFib[2][2])%MOD;
        for(long long int i=1;i<=2;i++)
            for(long long int j=1;j<=2;j++)
                matFib[i][j]=matNou[i][j];
    }
    ///cout<<matFib[1][1]<<' '<<matFib[1][2]<<'\n'<<matFib[2][1]<<' '<<matFib[2][2]<<'\n';
    ///cout<<'\n';
}
int main()
{
    long long int n;
    f>>n;
    matFib[1][1]=1;
    matFib[1][2]=1;
    matFib[2][1]=1;
    if(n==1)
        g<<1;
    else if(n==2)
        g<<1;
    else
        {
            Putere(n-1);
            g<<matFib[1][1]%666013;
            ///cout<<"REZ FINAL:\n";
            ///cout<<matFib[1][1]<<' '<<matFib[1][2]<<'\n'<<matFib[2][1]<<' '<<matFib[2][2]<<'\n'<<'\n';
        }
}