Description

一个整数总可以拆分为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。