Given a number

n, find the decimal value of the number formed by concatenating the binary representations of firstnnatural numbers.

Print answer modulo 10^9+7.

Also, *n* can be as big as 10^9 and hence logarithmic time approach is needed.

Eg: *n*=`4`

, Answer = `220`

**Explanation**: Number formed=`11011100`

(`1=1`

,`2=10`

,`3=11`

,`4=100`

).
Decimal value of `11011100`

=`"220"`

.

The code I am using below only works for first integers **N<=15**

String input = ""; for(int i = 1;i<=n;i++) { input += (Integer.toBinaryString(i)); } return Integer.parseInt(input,2);

## Answer

Note that working with string representation is not necessary (moreover, is not useful after task changing). Look at approach with bitwise arithmetics (Python, but principle is the same)

With new condition concerning modulo 1000000007 we have just add modulo operation to result calculation line at every step, because shift left and or-ing is equivalent to multiplication by power of two and adding, these operations are obeyed to equivalence relations for modulo properties. Note that intermediate results don’t exceed `1000000007*n`

, so **long** type is suitable here for reasonable n values.

n = 100 size = 0 #bit length of addends result = 0 # long accumulator for i in range(1, n + 1): if i & (i - 1) == 0: #for powers of two we increase bit length size += 1 result = ((result << size) | i) % 1000000007 #shift accumulator left and fill low bits with new addend print(result)

variant without bitwise operations:

pow2 = 1 nextpow = 2 result = 0 # long accumulator for i in range(1, n + 1): if i == nextpow: #for powers of two we increase bit length pow2 = nextpow nextpow = nextpow * 2 result = (result * pow2 + i) % 1000000007 #shift accumulator left and fill low bits with new addend