#include<bits/stdc++.h>
#define N 10
#define int long long
#define MOD 666013
using namespace std;

int M[N][N], a[N][N];
int n,p;

void mult(int a[N][N], int b[N][N], int n) {
    int c[N][N];
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            int s=0;
            for (int k=1; k<=n; ++k) {
                s+=a[i][k]*b[k][j];
            }
            c[i][j]=s%MOD;
        }
    }
   for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j) a[i][j]=c[i][j];
}

int32_t main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin>>n;
    mult(M,a,2);
    p=n;
    a[1][1]=a[2][2]=1;
    M[1][2]=M[2][1]=M[2][2]=1;
    for (int i=0; (1<<i)<=p; ++i) {
        if ((1<<i) & p) {
            mult(a,M,2);
        }
        mult(M,M,2);
    }
    cout<<(a[1][2])%MOD;


    return 0;
}