This solution to this question requires O(N) time. Luckily this can be solved in O(logN) time. Also, this is the A047778 sequence:
1,6,27,220,1765,14126,113015,1808248,28931977, 462911642,7406586283,118505380540,1896086088653, 30337377418462,485398038695407,15532737238253040, 497047591624097297,15905522931971113522
The sequence follows this recurrence relation:
where ?.? is floor function
a(n) can also be expressed as sum of multiple arithmetico–geometric series.
If we are interested in a(14), here's how it can be calculated.
Multiplying with powers of two on both sides of the above equations gives equations like the following:
If we add all the above equations, a(14) can be expressed as sum of four arithmetico–geometric series.
It's important to note that in all sequences except the first one, the first term of the arithmetic progression is of form 
and the last term 
The sum of n terms of arithmetico–geometric sequence can be calculated using this formula : 
a(First term of AP), n(Number of terms), d(Common Difference of AP), b(First term of GP), r(Common ratio of GP).
Since we're interested in a(n) mod 1000000007 and not the actual term a(n), these modulo arithmetics may come in handy.
This is a good starting point for implementing division modulo which requires some number theory basics.
Once we figure out the number of sequences required and the five variables a, n, d, b, r for each sequence, a(n) modulo 1000000007 can be calculated in O(logn) time.
Here's a working C++ code :
#include <numeric>
#include <iostream>
#define mod long(1e9+7)
long multiply(long a,long b){
a%= mod;b%= mod;
return (a*b)%mod;
}
void inverseModulo(long a,long m,long *x,long *y){ //ax congruent to 1 mod m
if(!a){
*x=0;
*y=1;
return ;
}
long x1,y1;
inverseModulo(m%a,a,&x1,&y1);
*x=y1-(m/a)*x1;
*y=x1;
return;
}
long moduloDivision(long a,long b,long m){ // (a*(returnValue))mod m congruent to b mod m
//https://www.geeksforgeeks.org/modular-division/ and https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
long x,y;
inverseModulo(b, m, &x, &y);
x%=m;
return (x*a)%m;
}
long power(long n,long r){ //calculates (n^r)%mod in logarithmic time
if(r==0) return 1;
if(r==1) return n;
if(r%2){
auto tmp=power(n, (r-1)/2);
return multiply(multiply(n,tmp),tmp);
}
auto tmp=power(n, r/2);
return multiply(tmp, tmp);
}
long sumOfAGPSeries(long a,long d,long b,long r,long n){
if(r==1) return multiply(n, multiply(a, 2)+multiply(n-1, d))/2;
long left=multiply(multiply(d, r), power(r,n-1)-1);
left=a+moduloDivision(left,r-1,mod);
left=multiply(left, b);
left%=mod;
long right=multiply(multiply(b, power(r, n)), a+multiply(n-1, d));
long ans=right-left;
ans=(ans%mod + mod) % mod;
return moduloDivision(ans,r-1,mod);
}
signed main(){
long N=1000;
long ans = 0;
long bitCountOfN = log2(N) + 1;
long nearestPowerOfTwo = pow(2, bitCountOfN - 1);
long startOfGP = 0;
while (nearestPowerOfTwo) { // iterating over each arithmetico–geometric sequence
long a, d, b, r, n;
a = N;
d = -1;
b = power(2, startOfGP);
r = power(2, bitCountOfN);
n = N - nearestPowerOfTwo + 1;
ans += sumOfAGPSeries(a, d, b, r, n);
ans %= mod;
startOfGP += n * bitCountOfN;
N = nearestPowerOfTwo - 1;
nearestPowerOfTwo >>= 1;
bitCountOfN--;
}
std::cout << ans << std::endl;
return 0;
}
The validity of the above C++ code can be verified using this trivial python code :
def a(n):
return int("".join([(bin(i))[2:] for i in range(1, n+1)]), 2)
for n in range(1,100):
print (a(n)%1000000007)
