An *odious* number is a non-negative integer that has an odd number of 1s in its binary representation. The first few odious numbers are therefore 1 ("1"), 2 ("10"), 4 ("100"), 7 ("111"), 8 ("1000"), 11 ("1011"), and so on.

Given an integer k, find and return the sum of the first k *odious* numbers, modulo 10^{6} + 7.

**Example**

For k = 4, the output should be

sumOdious(4) = 14.The sum of the first 4

*odious*numbers is 1 + 2 + 4 + 7 = 14.For k = 10, the output should be

sumOdious(10) = 95.

**Input/Output**

**[time limit] 4000ms (js)**

**[input] integer k***Guaranteed Constraints:*

1 ≤ k ≤ 10^{9}.**[output] integer**The sum of the first k

*odious*numbers, modulo 10^{6}+ 7.

## Solution

This problem can be tackled by observing the pattern the series generates. For that, we implement the actual problem statement naively.

```
function count(n) {
var s = 0;
while (n) s+= n & 1, n>>= 1;
return s;
}
function sumOdious(n) {
var s = 0;
var c = 0;
for (var i = 1; c < n; i++)
if (count(i) & 1) {
s+= i;
c++;
}
return s % (1e6 + 7);
}
for (var i=0; i <= 10; i++) {
console.log(i, sumOdious(i))
}
```

After executing the code, we see the following series:

\[\{1, 3, 7, 14, 22, 33, 46, 60, ...\}\]

Looking up the pattern reveals the known series A173209 with the following closed form solution:

\[a(n) = n^2 - (n + 1) \backslash 2 + \min(n \bmod 2, \text{hammingWeight}(n) \bmod 2)\]

We need the parity of the hamming weight here, which can be calculated recursively quite easily under the module two:

`h = x => x ? 1 + h(x >> 1) & 1: 0`

Given \(h\), the minimum of the parity of the hamming weight and \(n \bmod 2\) is simply

\[\min(n \bmod 2, \text{hammingWeight}(n) \bmod 2) := n \& 1 \& h(n) \]

Since we calculate everything under mod 2 already, we can remove the mod two from the \(h\) function:

`h = x => x ? 1 + h(x >> 1) : 0`

Finally, we can implement the whole solution:

```
m = 1e6 + 7
sumOdious = n =>
(n % m * n + (n & 1 & h(n)) - (++n >> 1)) % m
```

There is one little optimization possible: We can move the definition of the \(h\)-function into sumOdious.

```
m = 1e6 + 7
sumOdious = n =>
(n % m * n + (h = x => x ? n & 1 ^ h(x >> 1) : 0)(n) - (++n >> 1)) % m
```