#include <stdio.h>
__int64 ans[1000001];

void init()
{
	int i;
	ans[1] = 1;
	ans[2] = 2;
	for (i = 3; i < 1000001; i++)
	{
		if (i % 2)
		{
			ans[i] = ans[i - 1];
		}
		else
		{
			ans[i] = ans[i - 2] + ans[i / 2];
		}
		ans[i] %= 1000000000;
	}
}
int main()
{
	int X;
	init();
	while (scanf("%d", &X) != -1)
	{
		printf("%d\n", ans[X]);
	}
	return 0;
}