#include <fstream>
#define mod 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int pr(int e,int f,int g,int h)
{
    return ((long long)e%mod*(f%mod)+(long long)g%mod*(h%mod))%mod;
}
int main()
{
    int n,a=0,b=1,c=1,d=1;
    int x11=1,x12=0,x21=0,x22=1;
    in>>n;
    n--;
    while(n)
    {
        if(n%2)
        {
            int x1=pr(a,x11,c,x12);
            int x2=pr(b,x11,d,x12);
            int x3=pr(a,x21,c,x22);
            int x4=pr(b,x21,d,x22);
            x11=x1;
            x12=x2;
            x21=x3;
            x22=x4;
        }
        n>>=1;
        int x1=pr(a,a,b,c);
        int x2=pr(a,b,b,d);
        int x3=pr(a,c,c,d);
        int x4=pr(b,c,d,d);
        a=x1;
        b=x2;
        c=x3;
        d=x4;
    }
    out<<x22;
    return 0;
}