#include <bits/stdc++.h>
#define mod 666013

using namespace std;

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

struct matrix{
    vector<vector<int>> mat = vector<vector<int>>(2, vector<int>(2, 0));
    matrix operator * (const matrix &other) const{
        matrix product;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                for(int k = 0; k < 2; k++)
                    product.mat[i][j] = (product.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % mod;
        return product;
    }
    matrix power(int b){
        matrix product, a = *this;
        for(int i = 0; i < 2; i++)
            product.mat[i][i] = 1;
        while(b){
            if(b & 1)
                product = product * a;
            a = a * a;
            b >>= 1;
        }
        return product;
    }
};

matrix m, z;

void solve(int k){
    m.mat[0][1] = 1;
    z.mat[0][1] = 1, z.mat[1][0] = 1, z.mat[1][1] = 1;
    matrix a = m * z.power(k - 1);
    fout << a.mat[0][1];
}

int main()
{
    int k;
    fin >> k;
    solve(k);
    return 0;
}