#include <iostream>
using namespace std;
int main()
{
    int n=1000000000;
    unsigned long long a=1,b=1,c=2;
    for(int i=1;i<=n/3;i++)
        {
            a=(b+c)%666013;
            b=(a+c)%666013;
            c=(a+b)%666013;
        }
    n=n%3;
    if(n==1)
        cout<<a;
    if(n==2)
        cout<<b;
    if(n==0)
        cout<<c;
    return 0;
}