#include <bits/stdc++.h>

using namespace std;
const int mod = 666013;
typedef long long ll;
typedef struct matrix{
ll A[3][3];
};
static inline matrix mul(matrix a,matrix b){
matrix c;
c.A[1][1]=(b.A[1][1]*a.A[1][1]%mod+b.A[1][2]*a.A[2][1]%mod)%mod;
c.A[1][2]=(b.A[1][1]*a.A[1][2]%mod+b.A[1][2]*a.A[2][2]%mod)%mod;
c.A[2][1]=(b.A[2][1]*a.A[1][1]%mod+b.A[2][2]*a.A[2][1]%mod)%mod;
c.A[2][2]=(b.A[2][1]*a.A[1][2]%mod+b.A[2][2]*a.A[2][2]%mod)%mod;
return c;
}
matrix a,b;
inline int expo(int k){
matrix ans=a;
while(k){
    if(k&1)
        ans=mul(ans,a);
    a=mul(a,a);
    k>>=1;
}
return ans.A[1][1];
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    a.A[1][2]=1;
    a.A[2][1]=1;
    a.A[2][2]=1;
    a.A[1][1]=0;
    scanf("%d ",&k);
    printf("%d",expo(k));
}