单点时限: 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) \mod 1000000000$。
第 $1$ 行：一个整数 $T$ ($1 \le T \le 10$) 为问题数。
接下来 $T$ 行，每行输入一个正整数 $n(1≤n≤1000000)$。
对于每个问题，输出一行问题的编号（$0$ 开始编号，格式：case #0: 等）。
然后对应每个问题在一行中输出 $f(n) \mod 1000000000$。
3 7 9 46
case #0: 6 case #1: 10 case #2: 598