#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define l long
#define d double
#define fo(i, n) for (i = 0; i < n; i++)
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<pii> vpii;
#define infile "kfib.in"
#define outfile "kfib.out"
#define MODULO 666013
#define input ifstream fin(infile);
#define output ofstream fout(outfile);

input;
output;
typedef int matrix[2][2];
void mult(matrix a,matrix b)
{
    matrix c= {{0,0},{0,0}};
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
            {
                c[i][j]=(1LL*a[i][k]*b[k][j]+c[i][j])%666013;
            }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j]=c[i][j];
}
void expo(matrix a,long long b)
{
    matrix r= {{1,0},{0,1}};
    while(b!=0)
    {
        if(b%2)
            mult(r,a);
        mult(a,a);
        b/=2;
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j]=r[i][j];
}
int main()
{
    long long k;
    matrix p= {{0,1},{1,1}};
    fin>>k;
    expo(p,k);
    fout<<p[1][0]%666013;
    return 0;
}