#include<stdio.h>
#define MAX 10e5+10
#define MOD 10e8
long long a[MAX];
void fun();
int main()
{
int n;
fun();
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",a[n]);
}
}
void fun()
{
int i;
a[1]=1;
a[2]=2;
for(i=3;i<=MAX;i++)
{
if(i&1) a[i]=a[i-1];
else a[i]=(a[i-2]+a[i/2])%MOD;
}
}
