#include using namespace std; #define rep(i, n) for (int i=0; i> lr; Mo(int N) : N(N) {} void add(int l, int r) { // 0-indexed, [l, r] lr.emplace_back(l, r); } void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) { int Q = lr.size(); int W = N/min(N, (int)sqrt(Q)); // ブロック幅 vector ord(Q); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int x, int y) { int x_block = lr[x].first/W; int y_block = lr[y].first/W; if (x_block!=y_block) return x_blocklr[y].second : lr[x].secondlr[i].first) add_left(--l, r); while (rlr[i].second) erase_right(l, r--); out(i); } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); Cinit(); vector pow2 = {1}; int mult = 1; rep(i, 200010) { mult = 2*mult%MOD; pow2.pb((pow2.back()+mult)%MOD); } int T; cin >> T; Mo mo(200010); int Ns[T]; rep(i, T) { int N, M; cin >> N >> M; mo.add(M-1, N-1); Ns[i] = N; } int ans[T]; ll comb_sum = 1ll; auto add_left = [&](int l, int r) { comb_sum -= C(r, l+1); if (comb_sum<0) comb_sum += MOD; comb_sum %= MOD; }; auto add_right = [&](int l, int r) { comb_sum = (comb_sum*2%MOD-C(r-1, l))%MOD; if (comb_sum<0) comb_sum += MOD; comb_sum %= MOD; }; auto erase_left = [&](int l, int r) { comb_sum += C(r, l+1); comb_sum %= MOD; }; auto erase_right = [&](int l, int r) { comb_sum = (comb_sum+C(r-1, l))%MOD*inv[2]%MOD; if (comb_sum<0) comb_sum += MOD; comb_sum %= MOD; }; auto out = [&](int q) { ans[q] = comb_sum*pow2[Ns[q]-1]%MOD; }; mo.run(add_left, add_right, erase_left, erase_right, out); rep(i, T) cout << ans[i] << endl; }