python (log(n)) ^2 approach
\n\nO(logn) level to iterate \nin each level calculating result of power for O(logn)\n\n\nclass Solution(object):\n    def concatenatedBinary(self, n):\n       
![image](https://assets.leetcode.com/users/images/6dba8f5e-8013-4afc-a829-719065047032_1607360527.7108207.png)\n\nO(logn) level to iterate \nin each level calculating result of power for O(logn)\n\n```\nclass Solution(object):\n    def concatenatedBinary(self, n):\n        """\n        :type n: int\n        :rtype: int\n        """\n        def multiply(X, Y):\n            return [[sum(a*b for a,b in zip(X_row,Y_col)) % 1000000007 for Y_col in zip(*Y)] for X_row in X]\n        \n        ans, acc, level = [[1], [2], [1]], 1, 1\n        while acc < n:\n            M = 2 ** (level + 1)\n\t\t\t\n\t\t\t# number of matrix production in this level\n            x = take = min(n, M - 1) - acc\n            \n\t\t\tmat = [[M, 1, 0], [0, 1, 1], [0, 0, 1]]\n\t\t\t\n\t\t\t# for example\n\t\t\t# num^13 = num * num^4 * num^8\n\t\t\t# num^6 = num^2 * num^4\n            while x > 0:\n                if x & 1: ans = multiply(mat, ans)\n                mat, x = multiply(mat, mat), x >> 1\n            \n\t\t\tacc, level = acc + take, level + 1\n        \n        return ans[0][0]\n```\n\ncredit to @ckclark
[]