# 二的幂拆分计数

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

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由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

### 输入

```text
7
```

### 输出

```text
6
```

### 样例 2

### 输入

```text
8
```

### 输出

```text
10
```

### 样例 3

### 输入

```text
0
```

### 输出

```text
1
```

## 样例解释

样例一有六种：$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% | 无额外条件 |