Problem

Description

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

Input

A single line with a single integer, N.

Output

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample Input

Sample Output

Solution

DP 水题

记f[i]为考虑的数字为i时的方案数

易得当i为奇数时，与i-1方案数相同。i为偶数时，f[i] = f[i - 1] + f[i >> 1]。

根据此转移方程，易得代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 1000000 + 10
using namespace std;
int N;
int f[MAXN];
int main(int argc, char **Argv)
{
	ios::sync_with_stdio(false);
	cin >> N;
	f[1] = 1;
	for (int i = 2; i <= N; ++i)
		if (i & 1)
		{
			f[i] = f[i - 1];
		}
		else
		{
			f[i] = (f[i - 1] + f[i >> 1]) % 1000000000;
		}
	cout << f[N] << endl;
	return 0;
}