most overcomplicated python solution???
Approach\nCounted the total number of set bits within a range of numbers [1, n] to find the index of a certain number in the large array. Used binary search to 
# Approach\nCounted the total number of set bits within a range of numbers [1, n] to find the index of a certain number in the large array. Used binary search to get from an index to a number. Counted the frequency of certain bits within a range and multiplied each bit\'s frequency into a cumulative variable by using binary exponentiation under mod. The edge cases were the end points of the query\'s interval and I did those manually.\n\nI was so close to solving this in contest :_(\n\n# Complexity\n- Time complexity: O(log^2(n))\n\n- Space complexity: O(q) where q is number of queries\n\n# Code\n```py\nclass Solution:\n    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:\n        def fastpow(b, e, m):\n            if e == 0: return 1\n            t = fastpow(b, e >> 1, m)\n            if e & 1: return (b * (t * t) % m) % m\n            return (t * t) % m\n        \n        def countSetBits(n):\n            if n == 0: return 0\n            m = int(math.log2(n))\n            if n == ((1 << (m+1))-1):\n                return ((m+1) * (1 << m))\n            n -= (1 << m)\n            return (n + 1) + countSetBits(n) + (m * (1 << (m-1)))\n        \n        def getIndex(n):\n            return countSetBits(n-1)\n\n        def getNumber(idx):\n            lo, hi = 1, int(1e15)\n            while lo < hi:\n                mid = lo + ((hi - lo + 1) >> 1)\n                sidx = getIndex(mid)\n                if sidx > idx: hi = mid - 1\n                else: lo = mid\n            return lo\n        \n        def getBitCountN(n, b):\n            if b == 0: return n >> 1\n            tp = n >> b\n            cnt = (tp >> 1) << b\n            if tp & 1: cnt += n & ((1 << b) - 1)\n            return cnt\n        \n        def getBitCount(f, t, b):\n            return getBitCountN(t+1, b) - getBitCountN(f, b)\n        \n        def getPowerfulArr(n):\n            s = bin(n)[2:][::-1]\n            return [(1 << i) for i in range(len(s)) if int(s[i])]\n        \n        ans = []\n        for f, t, m in queries:\n            a, b = getNumber(f), getNumber(t)\n            if a == b:\n                c = getIndex(a)\n                t -= c; f -= c; cur = 1\n                pa = getPowerfulArr(a)\n                for i in range(f, t+1):\n                    cur *= pa[i]\n                    cur %= m\n                ans.append(cur)\n                continue\n            s, e, cur = a + 1, b - 1, 1\n            if e >= s:\n                for i in range(64):\n                    p = 1 << i\n                    cur *= fastpow(p, getBitCount(s, e, i), m)\n                    cur %= m\n            pa, pb = getPowerfulArr(a)[::-1], getPowerfulArr(b)\n            for i in range(t+1-getIndex(b)):\n                cur *= pb[i]\n                cur %= m\n            for i in range(getIndex(a+1)-f):\n                cur *= pa[i]\n                cur %= m\n            ans.append(cur)\n        return ans\n```
['Python3']