Python | Counting
Code\n\n#based on https://leetcode.com/problems/find-products-of-elements-of-big-array/solutions/5145201/c-bit-count-and-binary-search-clean-code-with-a-lot-exp
# Code\n```\n#based on https://leetcode.com/problems/find-products-of-elements-of-big-array/solutions/5145201/c-bit-count-and-binary-search-clean-code-with-a-lot-explanitions/\nclass Solution:\n    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:\n        def sumAndCountBitsUpToVal(val):\n            bitSum = 0\n            bitCnt = 0\n            bit = 0\n            j = 1\n            while j <= val:\n                cur = (val >> (bit+1)) << bit\n                cur += ((val%j)+1)*((val%(j<<1)) >= j)\n                bitCnt += cur\n                bitSum += bit*cur\n                j <<= 1\n                bit += 1\n            return bitSum, bitCnt\n        def getValueFromIndex(idx):\n            low, high = 1, 1<<50\n            while low < high:\n                mid = (low + high)//2\n                if sumAndCountBitsUpToVal(mid)[1] < idx:\n                    low = mid + 1\n                else:\n                    high = mid\n            return low\n        def prefixSumUpToIndex(idx):\n            val = getValueFromIndex(idx)\n            bitSum, bitCnt = sumAndCountBitsUpToVal(val)\n            while bitCnt > idx:\n                i = val.bit_length()\n                bitSum -= i-1\n                bitCnt -= 1\n                val -= (1<<(i-1))\n            return bitSum\n        return [pow(2, prefixSumUpToIndex(j+1)-prefixSumUpToIndex(i), mod) for i,j,mod in queries]\n        \n        \n```
['Python3']