using binary search
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\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```cpp []\nclass Solution {\npublic:\n    #define ll long long \n    ll binpow(ll a, ll n, ll m) {\n        a = a%m;\n        ll res = 1;\n        while (n) {\n            if (n & 1) {\n                res = (res * a) % m;\n                n--;\n            }\n            else {\n                n /= 2;\n                a = (a * a) % m;\n            }\n        }\n        return res;\n    }\n    void build(ll x, vector<ll>&cb) {\n        ll i = 1;\n        x++;\n        ll tot = 0;\n        ll f = 1;\n        while (f) {\n            ll cnt = x / (1ll << i);\n            ll rem = x % (1ll << i);\n            cnt = cnt * (1ll << (i - 1));\n            cnt += max(0ll, rem - (1ll << (i - 1)));\n            cb[i - 1] = cnt;\n            i++;\n            if (cnt == 0)f = 0;\n        }\n    }\n    ll cnt(ll x) {\n        x++;\n        ll i = 1;\n        ll tot = 0;\n        ll f = 1;\n        while (f) {\n            ll cnt = x / (1ll << i);\n            ll rem = x % (1ll << i);\n            cnt = cnt * (1ll << (i - 1));\n            cnt += max(0ll, rem - (1ll << (i - 1)));\n            tot += cnt;\n            i++;\n            if (cnt == 0)f = 0;\n        }\n        return tot;\n    }\n    ll f(ll r) {\n        ll lo = 0; ll hi = 1e15;\n        ll ans = 0;\n        auto chk = [&](ll x) -> bool {\n            ll tot = cnt(x);\n            // db(x, cnt(x));\n            return (tot - 1 <= r);\n        };\n        while (lo <= hi) {\n            ll mid = (lo + hi) >> 1;\n            if (chk(mid)) {\n                lo = mid + 1;\n                ans = mid;\n            }\n            else hi = mid - 1;\n        }\n        return ans;\n    }\n\n    vector<int> findProductsOfElements(vector<vector<long long>>& qry) {\n        ll q = size(qry);\n        vector<int>res(q);\n        for(int i=0;i<q;++i){\n            ll l,r,m;\n            l = qry[i][0];\n            r = qry[i][1];\n            m = qry[i][2];\n            // to find a y such that total number of set bits <= r-1\n            ll y = f(r);\n            // db(y);\n            vector<ll>cb1(63, 0), cb2(63, 0);\n            build(y, cb2);\n            if (cnt(y) - 1 <= r) {\n                ll left = r + 1 - cnt(y);\n                y++;\n                for (ll i = 0; i < 63; ++i) {\n                    if (((1ll << i) & y) && left) {\n                        cb2[i]++;\n                        left--;\n                    }\n                }\n            }\n            ll x = f(l - 1);\n            build(x, cb1);\n            if (cnt(x) <= l - 1) {\n                ll left = l - cnt(x);\n                x++;\n                // db(left, x);\n                for (ll i = 0; i < 63; ++i) {\n                    if (((1ll << i) & x) && left) {\n                        cb1[i]++;\n                        left--;\n                    }\n                }\n            }\n            for (ll i = 0; i < 63; ++i) {\n                cb2[i] = (cb2[i] - cb1[i]);\n            }\n            \n            ll ans = 1;\n            for (ll i = 0; i < 63; ++i) {\n                ll x = binpow((1ll << i), cb2[i], m);\n                ans = (ans * x) % m;\n            }\n            res[i] = ans;\n        }\n        return res;\n    }\n};\n```
['C++']