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

int n,a[2][2],b[2][2],c[2][2];

void fibb(int p) {
    a[2][2] = a[1][2] = a[2][1] = 1;
    b[1][1] = b[2][2] = 1;
    while(p) {
        if(p % 2) {
            c[1][1] = ((ll)a[1][1]*(ll)b[1][1]+(ll)a[1][2]*(ll)b[2][1])%mod;
            c[1][2] = ((ll)a[1][1]*(ll)b[1][2]+(ll)a[1][2]*(ll)b[2][2])%mod;
            c[2][1] = ((ll)a[2][1]*(ll)b[1][1]+(ll)a[2][2]*(ll)b[2][1])%mod;
            c[2][2] = ((ll)a[2][1]*(ll)b[1][2]+(ll)a[2][2]*(ll)b[2][2])%mod;
            b[1][1] = c[1][1];
            b[1][2] = c[1][2];
            b[2][1] = c[2][1];
            b[2][2] = c[2][2];
        }
        c[1][1] = ((ll)a[1][1]*(ll)a[1][1]+(ll)a[1][2]*(ll)a[2][1])%mod;
        c[1][2] = ((ll)a[1][1]*(ll)a[1][2]+(ll)a[1][2]*(ll)a[2][2])%mod;
        c[2][1] = ((ll)a[2][1]*(ll)a[1][1]+(ll)a[2][2]*(ll)a[2][1])%mod;
        c[2][2] = ((ll)a[2][1]*(ll)a[1][2]+(ll)a[2][2]*(ll)a[2][2])%mod;
        a[1][1] = c[1][1];
        a[1][2] = c[1][2];
        a[2][1] = c[2][1];
        a[2][2] = c[2][2];
        p /= 2;
    }
    printf("%d\n", b[2][2]);
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%d", &n);
    fibb(n-1);

    return 0;
}