二的幂拆分计数¶

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

仓库只提供大小为二的幂的标准零件包。装配员需要恰好凑出指定数量，并统计不同的包装组合。

(本故事由GPT-6重写)

给定非负整数 \(N\) .考虑所有有限的非降序列

\[ 2^{e_1},2^{e_2},\ldots,2^{e_t}, \qquad 0\le e_1\le e_2\le\cdots\le e_t, \]

要求其和恰好为 \(N\) .同一大小可以重复使用；同一多重集合的不同排列不产生新方案。

求方案数对 \(1000000000\) 取模的结果。空序列的和为零，因此 \(N=0\) 时有一种方案。

输入一行一个整数 \(N\) .

输出一行一个整数，表示方案数对 \(1000000000\) 取模的结果。

样例一有六种：\(1+1+1+1+1+1+1\) 、\(1+1+1+1+1+2\) 、\(1+1+1+2+2\) 、\(1+2+2+2\) 、\(1+1+1+4\) 、\(1+2+4\) .样例二有十种。样例三只有空序列。

\(0\le N\le2^{63}-1\) .幂的指数为非负整数。

分值比例	额外条件
100%	无额外条件