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

int main()
{
    int k,p;
    fin>>k;
    p=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(p)
    {
        if(p%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])%mod)%mod;
            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])%mod)%mod;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
        p/=2;
    }
    fout<<(b[2][2]%mod)%mod;
    return 0;
}