#include <cstdio>
#include <vector>
#define op %666013
using namespace std;
vector <int> v;
int main()
{
    int i=1,now;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    v.push_back(0);
    v.push_back(1);
    do{
        ++i;
        now=(v[i-1]+v[i-2])op;
        v.push_back(now);
    }while(!(v[i-1]==0 and v[i]==1));
    int per=i-1,k;
    //perioada este 1332028
    scanf("%d",&k);
    printf("%d\n",v[k%per]);
    return 0;
}