ZOJ Problem Set - 2872
Hadi loves binary numbers. So he likes to partition everything into powers of two. He wonders in how many ways he can partition a given number n into powers of two.
For example, there are 2 ways to partition 3: 1+1+1 and 1+2.
The first line of input consists of a single integer T, the number of test-cases. Each test-case consists of a line containing n. (0 <= n <= 2,000,000)
For each test-case, output a line containing number of ways in which n can be partitioned into binary numbers modulo 1,000,000.
Author: Hadi Moshayedi
Source: AUT Contest 1