传送门

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

1

7

Sample Output

1

6

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 1000000 + 10
using namespace std;
int N;
int f[MAXN];
int (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;
}