<p>Given an integer <code>n</code>, return <em>the <strong>decimal value</strong> of the binary string formed by concatenating the binary representations of </em><code>1</code><em> to </em><code>n</code><em> in order, <strong>modulo </strong></em><code>10<sup>9 </sup>+ 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
<strong>Explanation: </strong>&quot;1&quot; in binary corresponds to the decimal value 1. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 27
<strong>Explanation: </strong>In binary, 1, 2, and 3 corresponds to &quot;1&quot;, &quot;10&quot;, and &quot;11&quot;.
After concatenating them, we have &quot;11011&quot;, which corresponds to the decimal value 27.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 12
<strong>Output:</strong> 505379714
<strong>Explanation</strong>: The concatenation results in &quot;1101110010111011110001001101010111100&quot;.
The decimal value of that is 118505380540.
After modulo 10<sup>9</sup> + 7, the result is 505379714.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:

    long mod = 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);
    }

        int concatenatedBinary(int N) {
            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--;
                }

            return ans;
        }
    
};
8900