题目描述 一个整数总可以拆分为 $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$ (不超过 $1000000$)，输出 $f(n)\%1000000000$。 输入格式 每组输入包括一个整数：$N$ ($1<=N<=1000000$)。 （多组输入） 输出格式 对于每组数据，输出 $f(n)\%1000000000$。 输入样例 7 输出样例 6