#include<fstream>
using namespace std;
int i,n,a1,a2,a3;
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    n%=666013*2+2;
    a1=1;
    a2=1;
    for(i=3;i<=n;i++)
    {
        a3=(a1+a2)%666013;
        a1=a2;
        a2=a3;
    }
    g<<a3;
    return 0;
}