Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe array only has elements corresponding to set bits in numbers. To find the index in 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe array only has elements corresponding to set bits in numbers. To find the index in the big array, we need the sum of set bits upto n. \n\nTo find the final product we also need the position wise bit frequency upto (from-1) and (to) then we can use the difference to calculate the final product.\n\nFor any number n, these can be found with the following\n\n```\nfor(int i = 0; i<len; i++)\n{\n    long long period = 1LL << (i+1);\n    long long pos = period/2;\n    \n    sumsetbts[i] = (n/period)*(1LL << i) + max(0LL, n%period - pos + 1LL);\n}\n```\n\nTo find from and to, a binary search on the range 1 to 10^15 we can find the integer which has a sum of set bits (count of elements) <= some value including all the set bits upto its own representation.\n\nWe will take "some value" as from and to+1, because there is a count of from elements appearing before index from and to+1 elements appearing before and including index to, so the difference will keep [from..to] inclusive.\n\nNow the binary search result will only give us a number upto which the sum of set bits is <= the desired count. To get the desired count, we have to add bits from lsb to msb from the next number after the solution of binary search.\n\nCheck whether bits are set:\n\n```\nfor(int i = 0; i<60; i++)\n{\n    if(((n+1) >> i)&1)\n    {\n        a[i]++;\n        sum++;\n    }\n}\n```\n\nAlso needs modular exponentiation to calculate the final product.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // 1 2 1 2 4 1 4 2 4\n    const int len = 60;\n    const long long mx = 1e15 + 10;\n    \n    long long modexp(long long a, long long b, long long mod)\n    {\n        a %= mod;\n        long long ans = 1;\n        while(b > 0)\n        {\n            if(b%2)\n            {\n                ans = (ans*a)%mod;\n            }\n            \n            a = (a*a)%mod;\n            b /= 2;\n        }\n        \n        return ans;\n    }\n    \n    vector<long long> sumofsetbitsupto(long long n)\n    {\n        vector<long long> ans(len, 0);\n\n        for(int i = 0; i<len; i++)\n        {\n            long long period = 1LL << (i+1);\n            long long pos = period/2;\n            \n            ans[i] = (n/period)*(1LL << i) + max(0LL, n%period - pos + 1LL);\n        }\n\n        return ans;\n    }\n    \n    long long ssum(vector<long long>& a)\n    {\n        long long sum = 0;\n        for(int i = 0; i<a.size(); i++)\n        {\n            sum += a[i];\n        }\n        return sum;\n    }\n    \n    long long getnumberjustbeforepos(long long pos)\n    {\n        long long lo = 1;\n        long long hi = mx;\n        long long ans = -1;\n        \n        while(lo <= hi)\n        {\n            long long mid = lo + (hi - lo)/2;\n            vector<long long> a = sumofsetbitsupto(mid);\n\n            if(ssum(a) <= pos)\n            {\n                ans = mid;\n                lo = mid+1;\n            }\n            else\n            {\n                hi = mid-1;\n            }\n        }\n        \n        return ans;\n    }\n\n    vector<long long> getfreqbeforepos(long long n, long long pos)\n    {\n        vector<long long> a = sumofsetbitsupto(n);\n        long long sum = ssum(a);\n\n        if(sum < pos)\n        {\n            for (int i = 0; i<len; i++)\n            {\n                if(sum == pos)\n                {\n                    break;\n                }\n\n                if(((n+1) >> i)&1)\n                {\n                    a[i]++;\n                    sum++;\n                }\n            }\n        }\n\n        return a;\n    }\n    \n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {\n        //[1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]\n        //[0, 1, 0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 3]\n        \n        // to find index associated with certain actual number, need the sum of set bits for all numbers 1 to n-1\n        \n        // sum of set bits for bit pos i = n/(1 << i+1) + max(0, n%(1<<(i+1)) - 1<<i + 1)\n        vector<int> ans(queries.size());\n        \n        for(int i = 0; i<queries.size(); i++)\n        {\n            long long from = queries[i][0];\n            long long to = queries[i][1];\n            long long mod = queries[i][2];\n            \n            vector<long long> fpos_prefix = getfreqbeforepos(getnumberjustbeforepos(from), from);\n            vector<long long> tpos_prefix = getfreqbeforepos(getnumberjustbeforepos(to+1), to+1);\n\n            vector<long long> diff(len, 0);\n            \n            for(int i = 0; i<len; i++)\n            {\n                diff[i] = tpos_prefix[i] - fpos_prefix[i];\n            }\n            \n            long long product = 1;\n            \n            for(int i = 0; i<len; i++)\n            {\n                long long p = (1LL << i);\n                product = (product * modexp(p, diff[i], mod))%mod;\n            }\n            \n            ans[i] = (int)product;\n        }\n        \n        return ans;\n    }\n};\n```
['C++']