#include<stdio.h>
main(){
    __int64 n[100001];
    long i,j;
    n[1]=1;
    n[2]=2;

     for(i=3;i<100001;i++){
         if(n[i]%2==0)
            n[i]=n[i-2]+n[i/2];

         else{
            n[i]=n[i-1];
            n[i]=n[i]%100000000;

         }
     }
      scanf("%ld",&j);
      printf("%I64d\n",n[j]);
    return 0;
}

[ 本帖最后由 孤单旋律 于 2011-3-23 22:10 编辑 ]