#include <bits/stdc++.h>
#define DAU ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PLEC return 0;

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define cin fin
#define cout fout

#define N 2005
#define mod 666013
#define asa pair < pair < int , int > , pair < int , int > >
int n, rezultat;

asa putere_m(long long a, long long b, long long c, long long d, int n)
{
    if(n == 0)
    {
        return {{1,0},{0,1}};
    }
    if(n%2 == 1)
    {
        asa m = putere_m(a,b,c,d,n-1);
        long long a1 = m.first.first*a+m.second.first*b, b1 = m.first.second*a+m.second.second*b,
            c1 = m.first.first*c+m.second.first*d, d1 = m.first.second*c+m.second.second*d;
        a1 %= mod, b1 %= mod;
        c1 %= mod, d1 %= mod;
        return {{a1,b1},{c1,d1}};
    }
    long long a1 = a*a+c*b, b1 = b*(a+d),
        c1 = c*(a+d), d1 = d*d+c*b;
    a1 %= mod, b1 %= mod;
    c1 %= mod, d1 %= mod;
    return putere_m(a1,b1,c1,d1,n/2);
}

int main()
{
    cin >> n;
    if(n == 0)
    {
        cout << 0;
    }
    else if(n == 1)
    {
        cout << 1;
    }
    else
    {
        asa rez = putere_m(0,1,1,1,n-1);
        cout << rez.second.second;
    }
    PLEC
}