Video Explanation (With ALL proofs)
Explanation\n\nClick here for the video\n\n# Code\n\ntypedef long long int ll;\n\nclass Solution {\n    \n    ll CountOf2TillX (ll x) {\n        if (x <= 1) ret
# Explanation\n\n[Click here for the video](https://youtu.be/ku2RBhkBBIw)\n\n# Code\n```\ntypedef long long int ll;\n\nclass Solution {\n    \n    ll CountOf2TillX (ll x) {\n        if (x <= 1) return 0;\n        if (x == 2) return 1;\n        if (x == 3) return 2;\n        \n        ll largest_i = 0;\n         for (ll i = 2; i < 61; i ++) {\n            if ((1LL << i) <= x) continue;\n            largest_i = i;\n            break;\n        }\n        largest_i --;\n        \n        ll ans = (1LL << (largest_i-2))*largest_i*(largest_i-1);\n        ll lft = x - ((1LL << largest_i) - 1);\n        return (ans + lft*largest_i + CountOf2TillX(lft-1));\n    }\n    \n    ll TermsTillX (ll x) {\n        if (x == 0) return 0;\n        if (x == 1) return 1;\n        \n        ll largest_i = 0;\n         for (ll i = 0; i < 61; i ++) {\n            if ((1LL << i) <= x) continue;\n            largest_i = i;\n            break;\n        }\n        largest_i --;\n        \n        ll ans = (1LL << (largest_i-1))*largest_i;\n        ll lft = x - ((1LL << largest_i) - 1);\n        return (ans + lft + TermsTillX(lft-1));\n    }\n    \n    ll CountOf2TillIndex (ll ind) {\n        if (ind == 1) return 0;\n        \n        ll l = 0, r = 1e15;\n        while (l < r) {\n            ll m = (l+r) >> 1;\n            if (TermsTillX(m) >= ind) r = m;\n            else l = m+1;\n        }\n        if (TermsTillX(l) > ind) l --;\n        \n        ll ans = CountOf2TillX(l);\n        \n        ind -= TermsTillX(l);\n        for (int i = 0; ind > 0 && i < 61; i ++) {\n            if (((1LL << i) & (l+1)) == 0) continue;\n            ind --;\n            ans += i;\n        }\n        \n        return ans;\n    }\n    \n    ll FastPower (ll a, ll b, ll M) {\n        ll ans = 1;\n        while (b) {\n            if (b&1) ans = (ans * a) % M;\n            a = (a * a) % M;\n            b /= 2;\n        }\n        return ans % M;\n    }\n    \npublic:\n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {\n        vector<int> ans;\n        \n        for (auto q: queries) {\n            ll cnt_2 = CountOf2TillIndex(q[1]+1) - CountOf2TillIndex(q[0]);\n            ans.push_back(FastPower(2, cnt_2, q[2])); \n        }\n        return ans;\n    }\n};\n```
['C++']