一个整数总可以拆分为 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 种不同拆分方式。

用 f(n) 表示 n 的不同拆分的种数，例如 f(7)=6。

要求编写程序，读入 n，输出 f(n) mod 1e9。

一个正整数n。

一个整数，表示f(n) mod 1e9

4

4