#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
 long long int a,b,c,i,j;
 int x[21481][100001]={0};
 
 x[0][1]=1;
 x[0][2]=2;
 for(i=3;i<100000;i++)
 {x[0][i]=(x[0][i-1]+x[0][i-2])%10007;
 }
 for(j=1;j<=21480;j++){
 x[j][0]=(x[j-1][99999]+x[j-1][99998])%10007;
 x[j][1]=(x[j][0]+x[j-1][99999])%10007;
 
 for(i=2;i<100000;i++)
 {x[j][i]=(x[j][i-1]+x[j][i-2])%10007;
 }
 
 }
 while(scanf("%lld",&a)!=EOF)
 {b=a/100000;
 c=a%100000;
 
 printf("%d\n",x[b][c]);
  
 }
 return 0;
}

用Dev C++的編譯器都可以過