#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define lll long long
#define fi first
#define rest se.fi
#define suma se.se
#define sir first
#define se second
#define mod 666013
using namespace std;

const int NR = 2e5 + 10 , oo = 2e9 + 100  ;

void boost ()    {
    #ifndef ONLINE_JUDGE
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    #endif
     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}

void fib(lll n, lll&x, lll&y){
    if(n==0){
        x = 0;
        y = 1;
        return ;
    }

    if(n&1){
        fib(n-1, y, x);
        y=(y+x)%mod;
    }else{
        lll a, b;
        fib(n>>1, a, b);
        y = (a*a+b*b)%mod;
        x = (a*b + a*(b-a+mod))%mod;
    }
}

lll n ;
int main()  {
    lll i , j , x , y ;
    boost();
    cin >> n ;
    fib(n,x,y) ;
    cout << x << '\n' ;

}