#include <cstdio>
#define mod 666013
using namespace std;

struct mat {
    long long a11,a12,a21,a22;
};

mat init;
int n;

mat putlog(int p) {
    if (p <= 1) return init;
    mat ct = putlog(p/2);
    mat r;
    r.a11 = (ct.a11*ct.a11 + ct.a12*ct.a21)%mod;
    r.a12 = (ct.a11*ct.a12 + ct.a12*ct.a22)%mod;
    r.a21 = (ct.a11*ct.a21 + ct.a21*ct.a22)%mod;
    r.a22 = (ct.a12*ct.a21 + ct.a22*ct.a22)%mod;
    if (p%2==1) {
        ct = r;
        r.a11 = (ct.a11 + ct.a12)%mod;
        r.a12 = ct.a11;
        r.a21 = (ct.a21 + ct.a22)%mod;
        r.a22 = ct.a21;
    }
    return r;
}

int main() {
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    init.a11 = init.a12 = init.a21 = 1;
    scanf("%d",&n);
    mat fibn = putlog(n-1);
    printf("%d",fibn.a11);
}