#include <iostream>
#include <fstream>
using namespace std;

int r3(int putere)
{
    int rez=1,p3=3;
    do
    {
        if(putere%2)
            rez=((long long)rez*p3)%100003;
        p3=((long long)p3*p3)%100003;
        putere/=2;
    }while(putere);
    return rez;
}

void produsm(int a1[2][2],int b1[2][2],int c[2][2])
{//fac o copie in alte matrice lui a shi b, deoarece
//daca apelez sub forma produsm(rez,p,rez)
//calculul unui anumit c[i][j] produce instantaneu modificarea
//lui rez[i][j], ceea ce produce de fapt shi modificarea
//primului paramaetru adica a[i][j]
    int a[2][2],b[2][2],i,j,k;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++){a[i][j]=a1[i][j];b[i][j]=b1[i][j];}
    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]+(long long)a[i][k]*b[k][j])%666013;
        }
}

int r3m(int putere)
{
    int mp[2][2]={{0,1},{1,1}};
    int rez[2][2]={{0,1},{1,1}};
   //  int mp[2][2]={{1,0},{1,0}};
    do
    {
        if(putere%2)
            produsm(rez,mp,rez);
        produsm(mp,mp,mp);
        putere/=2;
    }while(putere);
return rez[0][0];

}

int main()
{
    int t,n,k,i,t1,t2,t3,tc;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
g<<r3m(n);

    return 0;
}