#include <fstream>
#define M 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
long long A[2][2];
int k;

void inm(long long  a[2][2], long long b[2][2])
{
    int x,y,z,t;
    x=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%M;
    y=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%M;
    z=(a[1][0]*b[0][0]+a[1][1]*b[0][1])%M;
    t=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%M;
    a[0][0]=x;
    a[0][1]=y;
    a[1][0]=z;
    a[1][1]=t;
}
void putere (long long a[2][2],int n, long long rez[2][2])
{
    if(n==0)
    {
        rez[0][0]=rez[1][1]=1;
        rez[0][1]=rez[1][0]=0;
        return;
    }
    putere(a,n/2,rez);
    inm(rez,rez);
    if (n%2==1) inm(rez,a);
}
int main()
{  long long B[2][2];
    in>>k;
    A[1][0]=A[0][1]=A[1][1]=1;
    putere(A,k,B);
    out<<B[0][1];
    return 0;
}