#include <fstream>
#include <iostream>

#define MOD 666013

using namespace std;

ifstream fin("kfib.in"); // m-am uitat putin si la explicatia de mai jos si am citit sper ca nu e o problema sau ceva
ofstream fout("kfib.out");

long long sa[2][2];
long long a[2][2]={{0, 1},
                   {0, 0}};
long long aja[2][2]={{0, 1},
                   {1, 1}};
int main()
{
    long long k,p,res=0;
    fin>>k;
    p=k-1;
    while (p){
        if (p%2==1){    // cand p impar cazul
            sa[0][0] = ((a[0][0]*aja[0][0])%MOD + (a[0][1]*aja[1][0])%MOD)%MOD;
            sa[0][1] = ((a[0][0]*aja[0][1])%MOD + (a[0][1]*aja[1][1])%MOD)%MOD;
            a[0][0] = sa[0][0];
            a[0][1] = sa[0][1];
        }
        sa[0][0] = ((aja[0][0]*aja[0][0])%MOD + (aja[0][1]*aja[1][0])%MOD)%MOD;
        sa[0][1] = ((aja[0][0]*aja[0][1])%MOD + (aja[0][1]*aja[1][1])%MOD)%MOD;
        sa[1][0] = ((aja[1][0]*aja[0][0])%MOD + (aja[1][1]*aja[1][0])%MOD)%MOD;
        sa[1][1] = ((aja[1][0]*aja[0][1])%MOD + (aja[1][1]*aja[1][1])%MOD)%MOD;
        aja[0][0] = sa[0][0];
        aja[0][1] = sa[0][1];
        aja[1][0] = sa[1][0];
        aja[1][1] = sa[1][1];
        p/=2;
    }
    res=a[0][1]%MOD;
    if(res<0)
      res+=MOD;
    fout<<res;
    return 0;
}