A heap is a full binary tree; for each node, its key is greater than its two sub-node’s key. Two heaps are different if there are two nodes which have different keys at the same location. Now we have a problem for you: tell me how many different N-Nodes heaps we can make with N integers?

There are many test cases; for each test case, one line contains only one integer N (1<=N<=1000000) indicating how many nodes the heap has.

For each test case, output one line contains an integer indicating the number of the kinds of the heaps. Because the result might be very large, you can just output the result modular 20000003.

#include<iostream>

#include<cstdio>

#define MX 1000010

using namespace std;

__int64 a[MX];

int main()

{

     __int64 i;

     __int64 n=5;

     a[1]=1;a[2]=1;

     for(i=3;i<MX-1;i++)

        a[i]=(a[i-1]+a[i-2])%20000003;

     while(~scanf("%lld",&n))

     {

       //  cout<<a[n]<<endl;

         printf("%lld\n",a[n]);

     }

     return 0;

}