GitHub 源文件 Markdown 中文

Partitions into Powers of Two

Estimated time limit: 0.5 seconds. Memory limit: 128 MB.

The deployed limit is the standard program’s largest input median in the target environment multiplied by \(2\) and rounded up to a multiple of \(0.5\) seconds. See the benchmark notes.

Story

A warehouse supplies standard packs whose sizes are powers of two. An assembler needs an exact total and wants to count the different pack combinations.

(This story was rewritten by GPT-6.)

Formal Problem Statement

For a nonnegative integer \(N\) , consider all finite nondecreasing sequences

\[ 2^{e_1},2^{e_2},\ldots,2^{e_t}, \qquad 0\le e_1\le e_2\le\cdots\le e_t, \]

with sum exactly \(N\) . A size may be used repeatedly. Reordering the same multiset does not create another solution.

Count these sequences modulo \(1000000000\) . The empty sequence sums to zero, so there is one solution when \(N=0\) .

Input

The input contains one integer \(N\) .

Output

Print the number of solutions modulo \(1000000000\) .

Samples

Sample 1

Input

7

Output

6

Sample 2

Input

8

Output

10

Sample 3

Input

0

Output

1

Sample explanations

The six solutions for sample one are \(1+1+1+1+1+1+1\) , \(1+1+1+1+1+2\) , \(1+1+1+2+2\) , \(1+2+2+2\) , \(1+1+1+4\) , and \(1+2+4\) . Sample two has ten solutions. Sample three has only the empty sequence.

Constraints and guarantees

\(0\le N\le2^{63}-1\) . Exponents are nonnegative integers.

Score	Additional constraints
100%	None