trilogy probability

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int MOD = 1e9 + 7;

ll mod_pow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

vector<int> solve(const vector<vector<int>>& q) {
    int mx = 1e6;
    vector<ll> dp(mx + 1, 0);

    for (int i = 2; i <= mx; ++i) {
        int h = i >> 1;
        if (i & 1) {
            dp[i] = (1LL + 2LL * dp[h]) % MOD;
        } else {
            dp[i] = (1LL + dp[h - 1] + dp[h]) % MOD;
        }
    }

    vector<int> res;
    res.reserve(q.size());

    for (const auto& r : q) {
        int l = r[0];
        int n = r[1] - l + 1;

        if (n == 1) {
            res.push_back(1);
        } else {
            ll k = dp[n];
            ll p = n - k;
            ll q_inv = mod_pow(n, MOD - 2, MOD);
            ll ans = (p * q_inv) % MOD;
            res.push_back((int)ans);
        }
    }

    return res;
}

int main() {
    int t;
    cin >> t;

    vector<vector<int>> intervals(t, vector<int>(2));
    for (int i = 0; i < t; ++i) {
        cin >> intervals[i][0] >> intervals[i][1];
    }

    vector<int> answers = solve(intervals);

    for (const int& ans : answers) {
        cout << ans << '\n';
    }

    return 0;
}