[[原文:http://acm.pku.edu.cn/JudgeOnline/problem?id=2229]]
----
''時間制限'':2000ミリ秒
''メモリ制限'':200000KB
&br;

*問題 [#kd371004]
農民であるジョンは、彼の牛に、「数Nが2の乗数の和として何通りの異なる方法で表せるか」を求めるよう命じた。2の乗数とは、1,2,4,8,...のように、2 k (kは0 <= kなる整数)として表せる数である。
例えば、N=7のとき、次の6通りの方法がある。
+ 1+1+1+1+1+1+1
+ 1+1+1+1+1+2
+ 1+1+1+2+2
+ 1+1+1+4
+ 1+2+2+2
+ 1+2+4

農民のジョンのために、数N(1 <= N <= 1,000,000)が2の乗数の和として何通りの異なる方法で表せるかを求めるプログラムを作成せよ。

*入力 [#u3564559]
入力は、整数Nを含む。

*出力 [#j4e7e5e0]
数Nが2の乗数の和として何通りの異なる方法で表せるかを出力せよ。この数値は大きいため、10進法において下9桁のみ出力せよ。 

*入力の例 [#c6f86d68]
 7

*出力の例 [#o47dec00]
 6

*原典 [#baa1e9d0]
USACO 2005 January Silver