#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD=666013;
int fib[1332029];
int main()
{
    int n,x=2;
    in>>n;
    fib[1]=1;
    fib[2]=1;
    while(fib[x]+fib[x-1]!=1)
    {
        fib[x+1]=fib[x]+fib[x-1];
        if(fib[x+1]>=MOD)
            fib[x+1]-=MOD;
        x++;
    }
    out<<fib[n%x];
    return 0;
}