The O(log(n) * log(n)) you need to know
The following is the O(log(n) * log(n)) solution which is faster than the O(n) and can work for very large n.\n\nMOD = pow(10, 9) + 7\n\ndef modInverse(n):\n   
The following is the `O(log(n) * log(n))` solution which is faster than the `O(n)` and can work for very large `n`.\n```\nMOD = pow(10, 9) + 7\n\ndef modInverse(n):\n    return pow(n, MOD - 2, MOD)\n\ndef sumGeometricSeries(r, n):\n    return (pow(r, n, MOD) - 1) * modInverse(r - 1)\n\ndef sumBinaryOfLength(n, r):\n    res = pow(2, n - 1, MOD) * sumGeometricSeries(pow(2, n, MOD), r - pow(2, n - 1, MOD) + 1)\n    res %= MOD\n    res += (sumGeometricSeries(pow(2, n, MOD), r - pow(2, n - 1, MOD) + 1) - 1 - (r - pow(2, n - 1, MOD))) * modInverse(pow(2, n, MOD) - 1)\n    return res % MOD\n\nclass Solution(object):\n    def concatenatedBinary(self, n):\n        curr_size = 1\n        res = 0\n        for b in range(n.bit_length(), 0, -1):\n            res += sumBinaryOfLength(b, min(n, pow(2, b) - 1)) * curr_size\n            res %= MOD\n            curr_size *= pow(2, (min(n, pow(2, b) - 1) - pow(2, b - 1) + 1) * b, MOD)\n            curr_size %= MOD\n        return (res + MOD) % MOD\n```
[]