Code: Down the Pivot

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

static const int MOD = 1'000'000'007;

int addmod(int a, int b) {
    int s = a + b;
    if (s >= MOD) s -= MOD;
    return s;
}

int submod(int a, int b) {
    int s = a - b;
    if (s < 0) s += MOD;
    return s;
}

int mulmod(long long a, long long b) {
    return int((a * b) % MOD);
}

int modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return int(r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    vector<pair<int, int>> qs(t);
    int max_n = 0;
    for (int i = 0; i < t; ++i) {
        int n, k;
        cin >> n >> k;
        qs[i] = {n, k};
        max_n = max(max_n, n);
    }

    const int LIM = 2 * max_n;
    vector<int> fact(LIM + 1), inv_fact(LIM + 1), inv_num(max_n + 2);
    fact[0] = 1;
    for (int i = 1; i <= LIM; ++i) fact[i] = mulmod(fact[i - 1], i);
    inv_fact[LIM] = modpow(fact[LIM], MOD - 2);
    for (int i = LIM; i >= 1; --i) inv_fact[i - 1] = mulmod(inv_fact[i], i);
    inv_num[1] = 1;
    for (int i = 2; i <= max_n + 1; ++i) {
        inv_num[i] = mulmod(MOD - MOD / i, inv_num[MOD % i]);
    }

    auto C = [&](int n, int r) -> int {
        if (r < 0 || r > n) return 0;
        return mulmod(fact[n], mulmod(inv_fact[r], inv_fact[n - r]));
    };

    // Number of ordered binary-tree shapes with m nodes: Catalan(m).
    vector<int> cat(max_n + 1, 0);
    for (int m = 0; m <= max_n; ++m) {
        int v = C(2 * m, m);
        v = mulmod(v, inv_num[m + 1]);
        cat[m] = v;
    }

    auto build_prefix_choose = [&](int n, int k) -> vector<int> {
        // pref[a] = sum_{i=0..k} C(a, i), for 0 <= a <= n.
        vector<int> pref(n + 1, 0);
        if (k < 0) return pref;
        pref[0] = 1;
        for (int a = 0; a < n; ++a) {
            int c = C(a, k);
            int nxt = submod(addmod(pref[a], pref[a]), c);
            pref[a + 1] = nxt;
        }
        return pref;
    };

    for (auto [n, k] : qs) {
        if (k < 0 || k > n) {
            cout << 0 << '\n';
            continue;
        }

        const int half = n - 1;
        vector<int> pref_k = build_prefix_choose(half, k);
        vector<int> pref_km2 = build_prefix_choose(half, k - 2);

        int ans = 0;
        for (int a = 0; a <= half; ++a) {
            int b = half - a;
            int ways_shape = mulmod(cat[a], cat[b]);

            int part1 = mulmod(pref_k[a], pref_k[b]);
            int part2 = mulmod(pref_km2[a], pref_km2[b]);
            int ways_label = submod(part1, part2);

            ans = addmod(ans, mulmod(ways_shape, ways_label));
        }

        cout << ans << '\n';
    }

    return 0;
}

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

template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    // coeff of a in x and y
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}

template <typename T> struct extended_gcd_result {
    T gcd;
    T coeff_a, coeff_b;
};
template <typename T> extended_gcd_result<T> extended_gcd(T a, T b) {
    T x = a, y = b;
    // coeff of a and b in x and y
    T ax = 1, ay = 0;
    T bx = 0, by = 1;
    while (x) {
        T k = y / x;
        y %= x;
        ay -= k * ax;
        by -= k * bx;
        std::swap(x, y);
        std::swap(ax, ay);
        std::swap(bx, by);
    }
    return {y, ay, by};
}

template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}

template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

  private:
    int v;

  public:
    modnum() : v(0) {}
    modnum(int64_t v_) : v(int(v_ % MOD)) {
        if (v < 0)
            v += MOD;
    }
    explicit operator int() const { return v; }
    friend std::ostream &operator<<(std::ostream &out, const modnum &n) {
        return out << int(n);
    }
    friend std::istream &operator>>(std::istream &in, modnum &n) {
        int64_t v_;
        in >> v_;
        n = modnum(v_);
        return in;
    }

    friend bool operator==(const modnum &a, const modnum &b) {
        return a.v == b.v;
    }
    friend bool operator!=(const modnum &a, const modnum &b) {
        return a.v != b.v;
    }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum &m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD - v : 0;
        return res;
    }
    friend modnum neg(const modnum &m) { return m.neg(); }

    modnum operator-() const { return neg(); }
    modnum operator+() const { return modnum(*this); }

    modnum &operator++() {
        v++;
        if (v == MOD)
            v = 0;
        return *this;
    }
    modnum &operator--() {
        if (v == 0)
            v = MOD;
        v--;
        return *this;
    }
    modnum &operator+=(const modnum &o) {
        v -= MOD - o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum &operator-=(const modnum &o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum &operator*=(const modnum &o) {
        v = int(int64_t(v) * int64_t(o.v) % MOD);
        return *this;
    }
    modnum &operator/=(const modnum &o) { return *this *= o.inv(); }

    friend modnum operator++(modnum &a, int) {
        modnum r = a;
        ++a;
        return r;
    }
    friend modnum operator--(modnum &a, int) {
        modnum r = a;
        --a;
        return r;
    }
    friend modnum operator+(const modnum &a, const modnum &b) {
        return modnum(a) += b;
    }
    friend modnum operator-(const modnum &a, const modnum &b) {
        return modnum(a) -= b;
    }
    friend modnum operator*(const modnum &a, const modnum &b) {
        return modnum(a) *= b;
    }
    friend modnum operator/(const modnum &a, const modnum &b) {
        return modnum(a) /= b;
    }
};

template <typename T> T pow(T a, long long b) {
    assert(b >= 0);
    T r = 1;
    while (b) {
        if (b & 1)
            r *= a;
        b >>= 1;
        a *= a;
    }
    return r;
}

using num = modnum<int(1e9) + 7>;

vector<num> fact, ifact;

void init() {
    int N = 2.1e6;
    fact.resize(N);
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = i * fact[i - 1];
    ifact.resize(N);
    ifact.back() = 1 / fact.back();
    for (int i = N - 1; i > 0; i--)
        ifact[i - 1] = i * ifact[i];
}

num ncr(int n, int k) {
    if (k < 0 || k > n)
        return 0;
    return fact[n] * ifact[k] * ifact[n - k];
}

void solve() {
    int N, K;
    cin >> N >> K;
    vector<num> cat(N + 1);
    for (int i = 0; i <= N; i++) {
        cat[i] = ncr(2 * i, i) / (i + 1);
    }
    N--;
    auto nless = [&](int A) -> num {
        if (A < 0)
            return 0;
        vector<num> prec(N + 1, 0);
        prec[0] = 1;
        for (int x = 1; x <= N; x++) {
            prec[x] = 2 * prec[x - 1] - ncr(x - 1, A);
        }
        num v = 0;
        for (int x = 0; x <= N; x++) {
            v += cat[x] * cat[N - x] * prec[x] * prec[N - x];
        }
        return v;
    };
    num ans = nless(K) - nless(K - 2);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int T;
    cin >> T;
    while (T--)
        solve();
}