一个整数总可以拆分为 $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$，输出 $f(n) \bmod 10^9$。

输入格式

一个整数 $n$。

输出格式

一个整数，表示 $f(n) \bmod 10^9$。

数据范围

$1 \le N \le 10^6$

输入样例：

7

输出样例：

6