問題一覧 > 通常問題

No.737 PopCount

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 110
作問者 : ei1333333 / テスター : beet
お気に入りにしたユーザー ProblemId : 2075 / 自分の提出
問題文最終更新日: 2018-09-28 01:10:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 200 (順位表) の他の問題:

Problem Statement

M-san, who loves $1$, defined the beauty $V(x)$ of a natural number $x$ as follows.

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

Here, $popcount(x)$ is defined as the number of occurrences of $1$ when $x$ is written in base $2$. For example, $popcount(23) = 4$. Written in base $2$, $23$ is $10111$, in which the number of occurrences of $1$ is $4$.

Given a natural number $N$, find $\displaystyle \sum_{i=1}^{N} V(i)$ modulo $10^9+7$.

Input

$N$

A natural number $N(1 \le N \le 10^{18})$ is given on $1$ line.

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
5
Output
23

We have $popcount(1) = 1, popcount(2) = 1, popcount(3) = 2, popcount(4) = 1, popcount(5)=2$.

Since $(1 \times 1) + (2 \times 1) + (3 \times 2) + (4 \times 1) + (5 \times 2) = 23$, the answer is $23$.

Sample 2
Input
30
Output
1333
Sample 3
Input
23072602871
Output
123456789

Note that the input $N$ may not fit in a 32bit integer type, and that the output must be the remainder after division by $10^9+7$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。