десятичное значение числа, образованное конкатенацией двоичных представлений первых n натуральных чисел

Обратите внимание, что работа со строковым представлением не обязательна (тем более бесполезна после смены задачи). Посмотрите на подход с побитовой арифметикой (Python, но принцип тот же)

С новым условием, касающимся модуля 1000000007, мы должны просто добавлять операцию по модулю в строку вычисления результата на каждом шаге, потому что сдвиг влево и операция "ИЛИ" эквивалентны умножению на степень двойки и сложения, эти операции подчиняются отношениям эквивалентности для свойств по модулю. Обратите внимание, что промежуточные результаты не превышают 1000000007*n, поэтому здесь подходит тип long для разумных значений n.

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)

вариант без побитовых операций:

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

Это решение этого вопроса требует O(N) времени. К счастью, это можно решить за O(logN) времени. Кроме того, это последовательность A047778:

1,6,27,220,1765,14126,113015,1808248,28931977, 462911642,7406586283,118505380540,1896086088653, 30337377418462,485398038695407,15532737238253040, 497047591624097297,15905522931971113522

Последовательность следует этому рекуррентному соотношению: , где ⌊.⌋ — это функция пола

a(n) также может быть выражено в виде суммы нескольких арифметико-геометрических рядов.

Если нас интересует a(14), вот как его можно рассчитать.

Умножение на степени двойки в обеих частях приведенных выше уравнений дает уравнения, подобные следующим:

Если сложить все вышеприведенные уравнения, a(14) можно выразить в виде суммы four арифметико-геометрического ряда.

Важно отметить, что во всех последовательностях, кроме первой, первый член арифметической прогрессии имеет вид и последний термин

Сумма n членов арифметико-геометрической последовательности может быть рассчитана по этой формуле :

a(First term of AP), n(Number of terms), d(Common Difference of AP), b(First term of GP), r(Common ratio of GP). 

Поскольку нас интересует a(n) mod 1000000007, а не фактический термин a(n), эта арифметика по модулю может пригодиться.

Это хорошая отправная точка для реализации деления по модулю, которое требует некоторых основ теории чисел.

Как только мы вычислим необходимое количество последовательностей и пять переменных a, n, d, b, r для каждой последовательности, a(n) modulo 1000000007 можно будет вычислить за O(logn) времени.

Вот рабочий код C++:

#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;
}

Действительность приведенного выше кода C++ можно проверить с помощью этого тривиального кода python:

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)