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

     for(i=3;i<1000001;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("%ld\n",n[j]);
    return 0;
}