[Usaco2005 Jan]Sumsets 求和

Farmer John 要求奶牛们寻找若干组数，使每组数之和等于给定的整数。每个使用的数都必须是 $2$ 的非负整数次幂，即 $1,2,4,8,\ldots$ 。同一组数可以重复使用，且不考虑加数的排列顺序。

例如，当 $N=7$ 时，共有以下 $6$ 种表示方法：

\begin{aligned} 7&=1+1+1+1+1+1+1,\\ 7&=1+1+1+1+1+2,\\ 7&=1+1+1+2+2,\\ 7&=1+1+1+4,\\ 7&=1+2+2+2,\\ 7&=1+2+4. \end{aligned}

请计算给定整数 $N$ 有多少种不同的表示方法。

输入格式

输入一个整数 $N$ 。

输出一个整数，表示方案数对 $10^9$ 取模后的结果。结果按通常的十进制整数格式输出，不补前导零。

本题为 USACO 2005 January 试题「Sumsets 求和」，题面与测试数据整理自 BZOJ。