题目描述 一个整数总可以拆分为 $ 2 $ 的幂的和。 例如： $ 7 $ 可以拆分为： $ 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 $ 总共有 $ 6 $ 种不同的拆分方式。 再比如 $ 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) \mod 1000000000 $。 输入格式 每组输入包括一个整数 $ N $（$ 1 \leq N \leq 1000000 $）。 （多组输入） 输出格式 对于每组数据，输出 $ f(n) \mod 1000000000 $。 输入样例 7 输出样例 6