No.737 PopCount

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : ei1333ei1333 / テスター : beetbeet
4 ProblemId : 2075 / 出題時の順位表

問題文

$1$ が大好きな M さんは, ある自然数 $x$ の美しさ $V(x)$ を次のように定義しました。

  • $V(x) = x \times popcount(x)$

ここで $popcount(x)$ は $x$ を $2$ 進表記したときに現れる $1$ の数と定義します。例えば $popcount(23) = 4$ です。$23$ を $2$ 進表記すると $10111$ で, これに現れる $1$ の数は $4$ 個です。

自然数 $N$ が与えられるので $\displaystyle \sum_{i=1}^{N} V(i)$ を $10^9+7$ で割った余りで求めてください。

入力

$N$

$1$ 行に自然数 $N(1 \le N \le 10^{18})$ が与えられます。

出力

$1$ 行に答えを出力してください。

サンプル

サンプル1
入力
5
出力
23

$popcount(1) = 1, popcount(2) = 1, popcount(3) = 2, popcount(4) = 1, popcount(5)=2$ です。

$(1 \times 1) + (2 \times 1) + (3 \times 2) + (4 \times 1) + (5 \times 2) = 23$ より $23$ が答えとなります。

サンプル2
入力
30
出力
1333
サンプル3
入力
23072602871
出力
123456789

入力の $N$ が 32bit整数型に収まらない場合があることや, $10^9+7$ で割った余りで出力することに注意してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。