T4 AC

using ll = long long;

class Solution {
    int fpow(ll a, ll p, ll m) {
        assert(p >= 0);
        ll ret = 1;
        ll cur = a;
        while(p) {
            if (p & 1)
                ret = ret * cur % m;
            cur = cur * cur % m;
            p >>= 1;
        }
        return int(ret % m);
    }
    ll gn(ll x) {
        // count the number of elements of first 2^x strong arrays;
        ll ret = 0;
        // cout << "gn(" << x << "): ";
        for (ll i = 0; i < x; ++i) ret = ret * 2 + (1ll << i);
        // cout << ret << endl;
        return ret;
    }
    ll hn(ll x) {
        // count the sum of elements of first 2^x strong arrays;
        ll ret = 0;
        // cout << "hn(" << x << "): ";
        for (ll i = 0; i < x; ++i) ret = ret * 2 + (1ll << i) * i;
        // cout << ret << endl;
        return ret;
    }
    ll fn(ll x) {
        // cout << "\nx: " << x << endl;
        ll ret = 0, rem = x, v = 0, lg_sum = 0;
        for (ll i = 48, bits = 0; i >= 0; --i) {
            ll ec = 1ll << i;
            ll picked_num = bits * ec, pick_val = lg_sum * ec + hn(i);
            ll num_it = gn(i) + picked_num;
            if (num_it > rem) {
                continue;
            } else {
                // cout << "rem: " << rem << " num_it: " << num_it << " ec: " << ec << " gn(i): " << gn(i) << " picked_num: " << picked_num << " bits: " << bits << " pick_val: " << pick_val << " lg_sum: " << lg_sum << endl;
                rem -= num_it;
                bits += 1;
                v |= ec;
                lg_sum += i;
                ret += pick_val;
            }
        }
        // cout << "rem: " << rem << " ret: " << ret << " x:" << x << " v: " << v << endl;
        if (rem) {
            // v += 1;
            while(rem && v) {
                ret += __builtin_ctzll(v & -v);
                v = v & (v - 1);
                rem -= 1;
            }
        }
        cout << "fn(" << x << "): " << ret << endl;
        return ret;
    }
    ll g(ll x) {
        // count the number of elements of first x strong array given x = 2^n;
        if (x == 0)  return 0;
        ll ret = 0;
        for (ll i = 0, v = 0; i <= x; i <<= 1, v += 1) {
            ret = ret * 2 + i;
        }
        return ret;
    }
    ll h(ll x) {
        // count the sum of elements of first x strong array given x = 2^n;
        // return (x - 1) * x / 2;
        ll t = x / 2;
        return (t + 1) * t;
    }
    ll f(ll x) {
        // count the sum of elements of first x elements in big_nums;
        cout << "\nx: " << x << endl;
        if (x == 0) return 1;
        ll ret = 0, rem = x, v = 0, lg_sum = 0;
        for (ll i = 31, bits = 0; i >= 0; --i) {
            ll ec = 1ll << i;
            ll picked_num = bits * ec, pick_val = lg_sum * g(ec) + h(ec);
            ll num_it = g(ec) + picked_num;
            if (num_it > rem) {
                continue;
            } else {
                cout << "rem: " << rem << " num_it: " << num_it << " ec: " << ec << " g(ec): " << g(ec) << " picked_num: " << picked_num << " bits: " << bits << " pick_val: " << pick_val << " lg_sum: " << lg_sum << endl;
                rem -= num_it;
                bits += 1;
                v |= ec * 2;
                lg_sum += i + 1;
                ret += pick_val;
            }
        }
        cout << "\nrem: " << rem << " ret: " << ret << " x:" << x << " v: " << v << endl;
        // rem -= 1;
        if (rem) {
            v += 1;
            while(rem && v) {
                // cout << rem << endl;
                ret += __builtin_ctz(v & -v);
                v = v & (v - 1);
                rem -= 1;
            }
        }
        cout << "f(" << x << "): " << ret <<endl;
        return ret;
    }
public:
    vector<int> findProductsOfElements(vector<vector<long long>>& qs) {
        assert(gn(0) == 0), assert(gn(1) == 1), assert(gn(2) == 4), assert(gn(5) == 80);
        assert(hn(0) == 0), assert(hn(1) == 0), assert(hn(2) == 2), assert(hn(3) == 12), assert(hn(4) == 48), assert(hn(5) == 160);
        // cout << "g(8): " << g(8) << " h(8): " << h(8) << endl;
        // cout << "f(2): " << f(2) << endl;
        // cout << "f(5): " << f(5) << endl;
        // cout << "fn(40): " << fn(40) << endl;
        int n = qs.size();
        vector<int> ret(n);
        for (int i = 0; i < n; ++i) {
            ll l = qs[i][0], r = qs[i][1], m = qs[i][2];
            // cout << "i: " << i << endl;
            ret[i] = fpow(2, fn(r + 1) - fn(l), m);
        }
        return ret;
    }
};