#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>

#define M 666013
#define N 2

using namespace std;

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

typedef long long ll;

typedef vector<vector<ll>> Matrix;
// a matrix is of shape nxn

// Multiply matrixes and returns the obtained matrix
// Also ,each element will be computed with % m
Matrix multiplyMatrix(const Matrix& a,const Matrix& b,const ll& m) {
    int n1 = a.size(), m1 = a[0].size(), n2 = b.size(), m2 = b[0].size();
    if (m1 != n2) {
        cout << "\nMatrixes cannot be multiplied";
        exit(0);
    }

    Matrix result(n1,vector<ll>(m2,0));
    
    // if(result.size()!=n1||(result.size()!=m2)){
    //     result.assign(n1, vector<ll>(m2, 0));
    // }

    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            ll sum = 0;
            for (int k = 0; k < n2; ++k) {
                sum =( sum + a[i][k] * b[k][j] ) % m;
            }
            result[i][j] = sum;
        }
    }

    return result;
}

// Same as above,but save the results on a directly
void multiplyMatrixOn(Matrix& a,Matrix& b,const ll& m){
    int n1 = a.size(), m1 = a[0].size(), n2 = b.size(), m2 = b[0].size();
    if (m1 != n2) {
        cout << "\nMatrixes cannot be multiplied";
        exit(0);
    }

    Matrix result(n1,vector<ll>(m2,0));

    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            ll sum = 0;
            for (int k = 0; k < n2; ++k) {
                sum =( sum + a[i][k] * b[k][j] ) % m;
            }
            result[i][j] = sum;
        }
    }


    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            a[i][j]=result[i][j];
        }
    }
}

Matrix matrixPower(Matrix a,ll power,const ll& m) {
    if (power == 1) {
        return a;
    }

    // Used for first update of a when we should multiply it 
    bool firstUpdate=1;

    Matrix copy=a;

    while(power){
        if(power&1){
            a=(firstUpdate?copy:multiplyMatrix(a,copy,m));
            firstUpdate=0;
        }
        copy=multiplyMatrix(copy,copy,m);
        power>>=1;
    }

    return a;
}

// Same as the above one,but uses multiplyMatrixOn
Matrix matrixPowerOn(Matrix a,ll power,const ll& m){
    if (power == 1) {
        return a;
    }

    int n=a.size();

    // Used for first update of a when we should multiply it 
    bool firstUpdate=1;

    Matrix copy=a;

    while(power){
        if(power&1){
            if(firstUpdate){
                a=copy;
                firstUpdate=0;
            }
            else{
                multiplyMatrixOn(a,copy,m);
            }
        }
        multiplyMatrixOn(copy,copy,m);
        power>>=1;
    }

    return a;
}

// Save on a the elements obtained by a*b multiplication
// We assume they have dimensions N x N, N defined above :(
void multiplyMatrixOn(ll a[N][N],ll b[N][N],const ll& m){
    ll result[N][N];
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            ll sum=0;
            for(int k=0;k<N;++k){
                sum=(sum+a[i][k]*b[k][j])%m;
            }
            result[i][j]=sum;
        }
    }

    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            a[i][j]=result[i][j];
        }
    }    
}

// Use static vectors to multiply,assume they have the form n x n
Matrix matrixPowerStaticVectors(Matrix matrix,ll power,const ll& m){
    if (power == 1) {
        return matrix;
    }

    ll a[N][N],copy[N][N];
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            copy[i][j]=matrix[i][j];
            a[i][j]=0;
            if(i==j){
                a[i][j]=1;
            }
        }
    }

    while(power){
        if(power&1){
            multiplyMatrixOn(a,copy,m);
        }
        multiplyMatrixOn(copy,copy,m);
        power>>=1;
    }

    Matrix result(N,vector<ll>(N));
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            result[i][j]=a[i][j];
        }
    }

    return result;
}


// Get the n-th Fibbonaci Number % m
// returns f_{n}%m 
ll getFibbonaciNumber(ll n,ll m){
    if (n <= 1) {
        return n%m;
    }

    Matrix dp;
    dp.assign(2, vector<ll>(2, 0));
    dp[0][1] = dp[1][0] = dp[1][1] = 1;

    Matrix initialValues;
    initialValues.assign(1, vector<ll>(2, 0));
    initialValues[0][1] = 1;

    // Matrix fibbonaci = multiplyMatrix(initialValues, matrixPower(dp, n, m), m);
    // Matrix fibbonaci = multiplyMatrix(initialValues, matrixPowerOn(dp, n, m), m);
    Matrix fibbonaci = multiplyMatrix(initialValues, matrixPowerStaticVectors(dp, n, m), m);
    return fibbonaci[0][0];
}


void Solve() {
    int n;
    fin >> n;

    fout << getFibbonaciNumber(n,M);
}

int main() {

    ios_base::sync_with_stdio(false);

    Solve();

    return 0;
}