#include <fstream>
#define modulo 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long a[6][6],b[6][6],c[6][6];

int main()
{
    int k,put;
    fin>>k;
    put=k-1;
    a[1][1]=0;a[1][2]=1;a[2][2]=1;a[2][1]=1;
    b[1][1]=1;b[1][2]=0;b[2][1]=0;b[2][2]=1;
    while(put)
    {
        if(put%2==1)
        {
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    for(int k=1;k<=2;k++)
                        c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%modulo)%modulo;
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                {
                    b[i][j]=c[i][j];
                    c[i][j]=0;
                }
        }
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    c[i][j]=(c[i][j]+(a[i][k]*a[k][j])%modulo)%modulo;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
        put/=2;
    }
    fout<<(b[2][2]%modulo)%modulo;
    return 0;
}