题目描述

一个整数总可以拆分为 $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(\leq 1000000)$，输出 $f(n)\%1000000000$。

输入格式