
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. Help Him. Input The first line of input consists of a single integer T, the number of testcases. Each testcase consists of a line containing n. (0 <= n <= 2,000,000) Output For each testcase, output a line containing number of ways in which n can be partitioned into binary numbers modulo 1,000,000. Sample Input
Sample Output
Author: Hadi Moshayedi Source: AUT Contest 1 