#include <bits/stdc++.h>
using namespace std;
#define NMAX 40
#define INF 1000000001
#define MOD 666013
#define pii pair<int,int>

#define STDIN 0
#if STDIN
    #define fein cin
    #define fout cout
#else
    ifstream fein("kfib.in");
    ofstream fout("kfib.out");
#endif

long long int x, y, z, a, b, c, n, t, test[2][2], res[2][2];

void prod(long long a[2][2], long long b[2][2], long long res[2][2], int n, int m, int p) {
    long long ans[2][2];
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            ans[i][j]=0;
        }
    }
    for(int k=0;k<n;k++) {
        for(int i=0;i<m;i++) {
            for(int j=0;j<p;j++) {
                ans[k][i]=(ans[k][i]+a[k][j]*b[j][i])%MOD;
            }
        }
    }
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            res[i][j]=ans[i][j];
        }
    }

}

void exp(long long a[2][2], int e) {
    long long ans[2][2];
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            ans[i][j]=0;
        }
    }
    ans[0][0]=1;
    ans[1][1]=1;

    for(int i=1;i<=e;i<<=1) {
        if(e&i) {
            prod(a, ans, ans, 2, 2, 2);
        }
        prod(a, a, a, 2, 2, 2);
    }
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            a[i][j]=ans[i][j];
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    long long k;
    fein>>k;

    test[0][0]=1;
    test[0][1]=1;
    test[1][0]=1;
    test[1][1]=0;
    res[0][0]=1;
    res[0][1]=1;
    exp(test, k-2);
    prod(res, test, res, 1, 2, 2);
    fout<<res[0][0];
    return 0;
}