#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct Mat{
    int m[3][3];
};

Mat p; int n;
int d = 666013;

Mat inmultire(Mat a, Mat b)
{
    Mat rez;
    rez.m[1][1] = (1ull*a.m[1][1]%d*b.m[1][1]%d)%d+(1ull*a.m[1][2]%d*b.m[2][1]%d)%d;
    rez.m[1][2] = (1ull*a.m[1][1]%d*b.m[1][2]%d)%d+(1ull*a.m[1][2]%d*b.m[2][2]%d)%d;
    rez.m[2][1] = (1ull*a.m[2][1]%d*b.m[1][1]%d)%d+(1ull*a.m[2][2]%d*b.m[2][1]%d)%d;
    rez.m[2][2] = (1ull*a.m[2][1]%d*b.m[1][2]%d)%d+(1ull*a.m[2][2]%d*b.m[2][2]%d)%d;
    return rez;
}

void showMat(Mat sh)
{
    for(int i=1; i<=2; i++, cout << '\n')
        for(int j=1; j<=2; j++)
            cout << sh.m[i][j] << ' ';
}

void logMat(Mat a, int n)
{
    while(n > 0)
    {
        if(n % 2)
            p = inmultire(p,a);
        a = inmultire(a,a);
        n/=2;
    }
    fout << p.m[1][1];
}

signed main()
{
    p.m[1][1]=0, p.m[1][2] = 1;
    p.m[2][1]=1, p.m[2][2] = 1;
    fin >> n;
    logMat(p,n);
    //showMat(p);
    return 0;
}