#include <iostream>
#include <fstream>
#include <vector>

#define MOD 666013
#define ll long long

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

class Matrix{
public:
    int n, m;
    vector<vector<ll> > w;

    Matrix(int n, int m, vector<vector<ll>> &x){
        this->n = n;
        this->m = m;
        this->w = x;
    }
    
    Matrix operator*(Matrix &other){
        int A = this->n;
        int B = this->m;
        int C = other.n;
        int D = other.m;
        
        vector<vector<ll>> f(A, vector<ll> (D));
        Matrix result(A, D, f);

        //dim(A, B) * dim(C, D) => dim(A, D)
        for(int k = 0; k<A; k++){
          for(int i = 0; i<D; i++){
            int tmp = 0;
            for(int j = 0; j<C; j++){
              tmp = tmp  + ((this->w[k][j] % MOD) * (other.w[j][i] % MOD)) % MOD; 
            }
            result.w[k][i] = tmp;
          }
        }
        
        return result;
    }

    Matrix operator^(int k){
        vector<vector<ll>> x(this->n, vector<ll>(this->m));
        for(int i = 0; i<x.size(); i++){
          for(int j = 0; j<x[i].size(); j++){
            if(i == j) x[i][j] = 1;
            else x[i][j] = 0;
          }
        }
        Matrix result(this->n, this->m, x);
        Matrix aux(this->n, this->m, this->w);
        while(k > 0){
            if(k & 1) result = result * aux;
            aux = aux * aux;
            k = k >> 1;
        }
        return result;
    }

    void print(){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++)
                cout << w[i][j] << " ";
            cout << "\n";
        }
    }
};

int main()
{
    int n;
    in >> n;
    //1, 1, 2, 3
    vector<vector<ll> > x {{1, 1}};
    vector<vector<ll> > y {{0, 1}, {1, 1}};
    Matrix st(1, 2, x);
    Matrix dr(2, 2, y);
    vector<vector<ll>> f(0, vector<ll> (0));
    Matrix result(1, 2, f);
    dr = dr ^ (n-2);
    result = st * dr;
    //result.print(); 
    out <<  result.w[0][1];
    return 0;
}