//#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>
 
using namespace std;
  
/********** TEMPLATE STARTS HERE ***********/
    
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) (int)v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define gcd __gcd 
#define FO(i, a) for(auto & i : a)
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);
#define digits(n) (int)(log10(n) + 1)
  
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pii> vii;
typedef vector <pll> vll;
    
const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;
    
template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
   
/*********** TEMPLATE ENDS HERE *************/
 
ifstream cin("kfib.in");
ofstream cout("kfib.out");
 
const int MOD = 666013;
 
#define int long long
 
int mat[5][5];
 
void prod(int a[5][5], int b[5][5])
{
    int t[5][5];
    t[1][1] = (a[1][1] * b[1][1] + a[1][2] * b[2][1]) % MOD;
    t[1][2] = (a[1][1] * b[1][2] + a[1][2] * b[2][2]) % MOD;
    t[2][1] = (a[2][1] * b[1][1] + a[2][2] * b[2][1]) % MOD;
    t[2][2] = (a[2][1] * b[1][2] + a[2][2] * b[2][2]) % MOD;
     
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            a[i][j] = t[i][j];
     
}
 
int v[5][5];
 
void lgput(int k)
{
    while(k > 0)
    {
        if(k & 1)
        {
            k--;
            prod(v, mat);
        }
        prod(mat, mat);
        k /= 2;
    }
}
 
main()
{
    mat[1][1] = 0;
    mat[1][2] = 1;
    mat[2][1] = 1;
    mat[2][2] = 1;
     
    v[1][1] = v[2][2] = 1;
     
    int k;
    cin >> k;
     
    if(k == 1)
        return cout << 1, 0;
     
    if(k == 2)
        return cout << 1, 0;
     
    k -= 2;
     
    lgput(k);
     
    cout << (v[1][2] + v[2][2]) % MOD;
}