题目描述

农夫约翰（Farmer John）命令他的奶牛们寻找不同的数字组合，使得这些数字的和等于给定的数 $N$。奶牛们只能使用 $2$ 的整数次幂的数字（即 $1, 2, 4, 8, 16, \dots$）。以下是数字 $7$ 的所有可能的组合方式：

1. $1 + 1 + 1 + 1 + 1 + 1 + 1$
2. $1 + 1 + 1 + 1 + 1 + 2$
3. $1 + 1 + 1 + 2 + 2$
4. $1 + 1 + 1 + 4$
5. $1 + 2 + 2 + 2$
6. $1 + 2 + 4$

请帮助 FJ 计算给定整数 $N$（$1 \leq N \leq 1,000,000$）的所有可能的表示方式的数量。由于这个数字可能非常大，只需输出其最后 $9$ 位数字（以十进制表示）。

输入格式

• 一行，包含一个整数 $N$。

输出格式

• 一个整数，表示 $N$ 的不同表示方式的数量（仅输出最后 $9$ 位数字）。

示例输入 1

7

示例输出 1

6

提示

输入解释：
$N = 7$，共有 $6$ 种不同的表示方式（如题目描述所示）。

输出解释：
直接输出 $6$，因为 $6$ 本身不超过 $9$ 位。

题目来源

USACO 2005 January Silver