#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int main(){
	 int a[1000005];
	int n;
	a[1]=1;
	a[2]=2;
	for(int i=3;i<=1000000;i++){
		if(i%2==1)
			a[i]=(a[i-1])%1000000000;
		else {
			a[i]=(a[i/2]+a[i-1])%1000000000;

		}

	}
	while(cin >>n){

		cout <<a[n]<<endl;

	}
	//system("pause");
	return 0;
}

奇数 第一个拆分的只能是1  而偶数则是1 和 2都行

1           1                                                                                                        

2           11  2&nbs...