Dotcpp编程2018年底狂欢赛_问题E

提交: 93 解决: 29

题目描述

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)

输入

The first line of the input contains the number of test cases in the file. And t he first line of each case

contains one integer numbers n

输出

For each test case, output a line with the ans % 1000000000.

样例输入

1
7

样例输出

提示

视频教学见视频网课

年底了，我们这次玩点不一样的！

第4~10名有奖

每个题目都用C/C++/JAVA提交通过有全能奖一个

比赛前最后一个提交并且正确的有顽强拼搏奖一个

博客栏发布本次比赛全部题目的题解的同学，最佳题解奖一个！

提交编号为618888、619999的有优秀奖!

更多奖项随时公布！