196. Concatenation of Consecutive Binary Numbers (String)

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 through n (in order), modulo 10^9+7.

Example: n=3 → '1'+'10'+'11' = '11011' = 27.

Input: A single integer n.

Output: An integer — the decimal value of the concatenated binary string, mod 10^9+7.

Examples

Input: 1
Output: 1
Explanation: Binary: '1' = 1.

Input: 3
Output: 27
Explanation: '1'+'10'+'11' = '11011' = 27.

Input: 12
Output: 505379714
Explanation: Concatenation of 1..12 in binary mod 10^9+7.

Constraints

• 1 <= n <= 10^5

Asked by