程序设计能力实训

1173. 数字拆分

单点时限: 2.0 sec

内存限制: 256 MB

将一个正整数拆分为成 $2$ 的幂的和,例如:

$7=1+2+4$

$7=1+2+2+2$

$7=1+1+1+4$

$7=1+1+1+2+2$

$7=1+1+1+1+1+2$

$7=1+1+1+1+1+1+1$

总共有六种不同的拆分方案。

再比如:$4$ 可以拆分成:$4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2$。

函数 $f(n)$ 表示 $n$ 的不同拆分的方案数,例如 $f(7)=6$。

请编写程序,读入一个正整数 $n$ ($1≤n≤1000000$),输出 $f(n)%1000000000$。

输入格式

第 $1$ 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

接下来 $T$ 行,每行输入一个正整数 $n(1≤n≤1000000)$。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出 $f(n)%1000000000$。

样例

Input
3
7
9
46
Output
case #0:
6
case #1:
10
case #2:
598
不限期开放

题目列表