Farmer John は指定された数になる異なる数の集合を探すよう牛に命じました。使うのは 2 の整数乗だけです。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
整数 $N$（$1 \le N \le 1{,}000{,}000$）のすべての表し方を数えて FJ を助けてください。
一行に整数 $N$ 一つ。
$N$ を指定の和で表す方法数。非常に大きくなり得るため、十進表記の下 9 桁だけを出力してください。
76問題 1：和の表し方
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: