T4WA

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 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 = 1; i <= x; i <<= 1) {
            ret = ret * 2 + i;
        }
        return ret;
    }
    ll h(ll x) {
        // count the sum of elements of first x strong array;
        // 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;
        for (ll i = 31, bits = 0; i > 0; --i) {
            ll ec = 1ll << (i - 1);
            ll picked_num = bits * ec, pick_val = v * 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 << endl;
                rem -= num_it;
                bits += 1;
                v |= ec;
                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) {
        // cout << "g(8): " << g(8) << " h(8): " << h(8) << endl;
        // cout << "f(2): " << f(2) << endl;
        // cout << "f(5): " << f(5) << 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, f(r + 1) - f(l), m);
        }
        return ret;
    }
};