#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n,putere;
long long a[4][4],b[4][4];
void inm(long long c[4][4],long long b[4][4])
{
    long long d[4][4];
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    d[i][j]=0;

    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                d[i][j]=(d[i][j]+(c[i][k]*b[k][j])%mod)%mod;
            }
        }
    }

    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++){
            c[i][j]=d[i][j];

        }

    }

}
void put(long long b[4][4],long long c[4][4],int n)
{
 while(n!=0)
 {
     if(n%2==1)
     {

         inm(c,b);

     }
     n=n/2;
     inm(b,b);
 }
}
int main()
{
    fin>>n;
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    b[1][1]=1;
    b[2][2]=1;
    put(a,b,n-1);
    fout<<b[1][1];



    return 0;
}