这题远远没有紫的难度

若 opt=1，那么很明显是要我们求 $\binom{n}{m}$。

若 opt=0，我们可以先求出连线严格下降的方案数，即上一问。答案是 $\binom{n}{m}$。

然后我们考虑将相同的元素插进这个序列。使用插板法可得答案是 $\binom{n+m-1}{m}$。

我的实现方式是使用定义 $\binom{n}{m}=\frac{\prod\limits_{i=m}^ni}{m!}$。上面直接暴力乘，下面快速阶乘算法 $\Theta(\sqrt{w}\log w)$ 预处理，$\Theta(\sqrt w)$ 单次询问（其中 $w$ 为 $m$ 的值域）。

由于本题模数固定，可以使用编译器自带取模优化（如果写三模数 NTT 那么内部可以采用蒙哥马利模乘加速）。

代码有一点长。已省略 cin,cout 的实现。

// #define __MY_USE_LONG_DOUBLE__
// @code long double is not used in this problem
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#include <cstdint>
#include <utility>
// here is cin,cout
namespace OY {
template <typename _ModType, _ModType _P>
struct Modular {
    static constexpr _ModType mod() { return _P; }
    static constexpr _ModType mod(uint64_t __a) { return __a % _P; }
    static constexpr _ModType plus(_ModType __a, _ModType __b) {
        if (__a += __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType minus(_ModType __a, _ModType __b) {
        if (__a += _P - __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType multiply(uint64_t __a, uint64_t __b) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return multiply_ld(__a, __b);
        else return multiply_64(__a, __b);
    }
    static constexpr _ModType multiply_64(uint64_t __a, uint64_t __b) { return mod(__a * __b); }
    static constexpr _ModType multiply_128(uint64_t __a, uint64_t __b) { return __uint128_t(__a) * __b % _P; }
    static constexpr _ModType multiply_ld(uint64_t __a, uint64_t __b) {
        if (std::__countl_zero(__a) + std::__countl_zero(__b) >= 64) return multiply_64(__a, __b);
        int64_t res = __a * __b - uint64_t(1.L / _P * __a * __b) * _P;
        if (res < 0) res += _P;
        else if (res >= _P) res -= _P;
        return res;
    }
    static constexpr _ModType pow(uint64_t __a, uint64_t __n) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return pow_ld(__a, __n);
        else return pow_64(__a, __n);
    }
    static constexpr _ModType pow_64(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_64(res, b);
            b = multiply_64(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_128(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_128(res, b);
            b = multiply_128(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_ld(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_ld(res, b);
            b = multiply_ld(b, b);
            __n >>= 1;
        }
        return res;
    }
    template <typename _Tp>
    static constexpr _Tp divide(_Tp __a) { return __a / _P; }
    template <typename _Tp>
    static constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) {
        _Tp quo = __a / _P, rem = __a - quo * _P;
        return {quo, rem};
    }
};
template <uint32_t _P>
using Modular32 = Modular<uint32_t, _P>;
template <uint64_t _P>
using Modular64 = Modular<uint64_t, _P>;
}
namespace OY {
template <typename _ModType, _ModType _P, bool _IsPrime = false>
struct StaticModInt {
    using mint = StaticModInt<_ModType, _P, _IsPrime>;
    _ModType m_val;
    static_assert(_P > 1 && _P < 1ull << 63);
    constexpr StaticModInt() : m_val(0) {}
    template <typename _Tp, std::enable_if_t<std::is_signed_v<_Tp>, bool> = true>
    constexpr StaticModInt(_Tp __val) : m_val(0) {
        int64_t x = int64_t(__val) % int64_t(mod());
        if (x < 0) x += mod();
        m_val = x;
    }
    template <typename _Tp, std::enable_if_t<std::is_unsigned_v<_Tp>, bool> = true>
    constexpr StaticModInt(_Tp __val) : m_val(__val % mod()) {}
    static constexpr mint raw(_ModType __val) {
        mint res;
        res.m_val = __val;
        return res;
    }
    static constexpr _ModType mod() { return _P; }
    constexpr _ModType val() const { return m_val; }
    constexpr mint pow(uint64_t __n) const { return Modular<_ModType, _P>::pow(m_val, __n); }
    constexpr mint inv() const {
        if constexpr (_IsPrime) return inv_Fermat();
        else return inv_exgcd();
    }
    constexpr mint inv_exgcd() const {
        _ModType x = mod(), y = m_val, m0 = 0, m1 = 1;
        while (y) {
            _ModType z = x / y;
            x -= y * z;
            m0 -= m1 * z;
            std::swap(x, y);
            std::swap(m0, m1);
        }
        if (m0 >= mod()) m0 += mod() / x;
        return raw(m0);
    }
    constexpr mint inv_Fermat() const { return pow(mod() - 2); }
    constexpr mint &operator++() {
        if (++m_val == mod()) m_val = 0;
        return *this;
    }
    constexpr mint &operator--() {
        if (m_val == 0) m_val = mod();
        m_val--;
        return *this;
    }
    constexpr mint operator++(int) {
        mint old(*this);
        ++*this;
        return old;
    }
    constexpr mint operator--(int) {
        mint old(*this);
        --*this;
        return old;
    }
    constexpr mint &operator+=(const mint &__other) {
        m_val = Modular<_ModType, _P>::plus(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator-=(const mint &__other) {
        m_val = Modular<_ModType, _P>::minus(m_val, __other.m_val);
            return *this;
    }
    constexpr mint &operator*=(const mint &__other) {
        m_val = Modular<_ModType, _P>::multiply(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator/=(const mint &__other) { return *this *= __other.inv(); }
    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
    constexpr bool operator==(const mint &__other) const { return m_val == __other.m_val; }
    constexpr bool operator!=(const mint &__other) const { return m_val != __other.m_val; }
    constexpr bool operator<(const mint &__other) const { return m_val < __other.m_val; }
    constexpr bool operator>(const mint &__other) const { return m_val > __other.m_val; }
    constexpr bool operator<=(const mint &__other) const { return m_val <= __other.m_val; }
    constexpr bool operator>=(const mint &__other) const { return m_val <= __other.m_val; }
    template <typename _Tp>
    constexpr explicit operator _Tp() const { return _Tp(m_val); }
    constexpr friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    constexpr friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    constexpr friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    constexpr friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    template <typename _Istream>
    friend _Istream &operator>>(_Istream &is, mint &self) { return is >> self.m_val; }
    template <typename _Ostream>
    friend _Ostream &operator<<(_Ostream &os, const mint &self) { return os << self.m_val; }
};
template <uint32_t _P, bool _IsPrime>
using StaticModInt32 = StaticModInt<uint32_t, _P, _IsPrime>;
template <uint64_t _P, bool _IsPrime>
using StaticModInt64 = StaticModInt<uint64_t, _P, _IsPrime>;
}
using mint = OY::StaticModInt32<1000000007, true>;
using std::vector;
#ifdef __MY_USE_LONG_DOUBLE__
#define double long double
#define llround llroundl
const double pi = acosl(-1.0L);
const double two = 2.0L;
#else
const double pi = acos(-1.0);
const double two = 2.0;
#endif
template <typename T>
struct cp_base {
    T m_real, m_imag;
    inline constexpr cp_base(const T& r, const T& i) : m_real(r), m_imag(i) {}
    inline constexpr cp_base(const T& r = T()) : m_real(r), m_imag(0) {}
    inline constexpr cp_base<T> operator+(const cp_base<T> &o) const
    { return cp_base<T>(m_real + o.m_real, m_imag + o.m_imag); }
    inline constexpr cp_base<T> operator-(const cp_base<T> &o) const
    { return cp_base<T>(m_real - o.m_real, m_imag - o.m_imag); }
    inline constexpr cp_base<T> operator*(const cp_base<T> &o) const
    { return cp_base<T>(m_real * o.m_real - m_imag * o.m_imag, m_real * o.m_imag + m_imag * o.m_real); }
    inline constexpr cp_base<T> conj() const
    { return cp_base<T>(m_real, -m_imag); }
    inline constexpr T real() const { return m_real; }
    inline constexpr T imag() const { return m_imag; }
    inline constexpr T& real() { return m_real; }
    inline constexpr T& imag() { return m_imag; }
};
typedef cp_base<double> cp;
static vector<size_t> rev;
vector<cp> omegas;
inline void get_rev(size_t len, int x) {
    if (len == rev.size()) return;
    rev.resize(len);
    for (size_t i = 0; i < len; i++) rev[i] = rev[i >> 1ull] >> 1ull | (i & 1ull) << x;
    omegas.resize(len);
    for (size_t i = 0; i < len; i++) omegas[i] = cp(std::cos(two * pi / len * i), std::sin(two * pi / len * i));
}
inline void FFT(vector<cp>& a, size_t n, bool type) {
    for (size_t i = 1ull; i < n; ++i) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
    for (size_t i = 2ull; i <= n; i <<= 1ull) for (size_t j = 0ull, l = (i >> 1ull), ch = n / i; j < n; j += i) for (size_t k = j, now = 0ull; k < j + l; k++) {
        cp x = a[k], y = a[k + l] * (type ? omegas[now] : omegas[now].conj());
        a[k] = x + y;
        a[k + l] = x - y;
        now += ch;
    }
    if (!type) {
        for (size_t i = 0; i < n; i++) {
            a[i].real() /= n;
            a[i].imag() /= n;
        }
    }
}
inline void mul(size_t n, size_t m, const vector<mint>& a, const vector<mint>& b, vector<mint>& c, size_t len) {
    const size_t up = sqrt(mint::mod());
    mint v1, v2, v3;
    vector<cp> P(len, cp(0, 0)), Q(len, cp(0, 0)), R(len, cp(0, 0));
    for (size_t i = 0ull; i < n; i++) P[i] = cp(a[i].val() % up, a[i].val() / up);
    for (size_t i = 0ull; i < m; i++) R[i] = cp(b[i].val() % up, b[i].val() / up);
    FFT(P, len, true);
    FFT(R, len, true);
    Q[0] = P[0].conj();
    for (size_t i = 1ull; i < len; i++) Q[i] = P[len - i].conj();
    for (size_t i = 0ull; i < len; i++) {
        P[i] = P[i] * R[i];
        Q[i] = Q[i] * R[i];
    }
    FFT(P, len, false);
    FFT(Q, len, false);
    c.resize(n + m - 1);
    for (size_t i = 0ull; i < n + m - 1; i++) {
        v1 = llround((P[i].real() + Q[i].real()) / two);
        v2 = llround((Q[i].real() - P[i].real()) / two);
        v3 = llround(P[i].imag());
        c[i] = v1 + v2 * up * up + v3 * up;
    }
}
static vector<mint> fac, mfac, invfac, minvfac, inv, minv;
inline void init(size_t n, mint m) {
    size_t tmp = n << 1ull | 1ull;
    tmp++;
    fac.resize(tmp);
    mfac.resize(tmp);
    invfac.resize(tmp);
    minvfac.resize(tmp);
    inv.resize(tmp);
    minv.resize(tmp);
    fac[0] = mfac[0] = 1ull;
    for (size_t i = 1ull; i < tmp; i++) {
        fac[i] = fac[i - 1ull] * i;
        mfac[i] = mfac[i - 1ull] * (m - n + i - 1ull);
    }
    tmp--;
    invfac[tmp] = fac[tmp].inv();
    minvfac[tmp] = mfac[tmp].inv();
    for (size_t i = tmp; i; i--) {
        invfac[i - 1ull] = invfac[i] * i;
        minvfac[i - 1ull] = minvfac[i] * (m - n + i - 1ull);
        inv[i] = invfac[i] * fac[i - 1ull];
        minv[i] = minvfac[i] * mfac[i - 1ull];
    }
    minv[0] = 1ull;
}
inline void LagrangeInterpolation_ex(size_t n, mint m, const vector<mint>& a, vector<mint> &b) {
    vector<mint> f, g;
    size_t len = 1ull;
    int x = -1;
    while (len < n * 3ull + 2ull) len <<= 1ull, x++;
    get_rev(len, x);
    f.resize(len);
    g.resize(len);
    init(n, m);
    for (size_t i = 0ull; i <= n; i++) {
        f[i] = invfac[i] * invfac[n - i] * a[i];
        ((n - i) & 1ull) && (f[i] = -f[i]);
    }
    for (size_t i = 0; i <= (n << 1); i++) g[i] = minv[i + 1];
    mul(n + 1ull, n << 1ull | 1ull, f, g, f, len);
    b.resize(n + 1ull);
    for (size_t i = n; i <= (n << 1ull); i++) b[i - n] = mfac[i + 1ull] * minvfac[i - n] * f[i];
}
static vector<mint> mc;
size_t sval;
inline void prepare(mint n) {
    static vector<mint> md;
    int pos = 0;
    sval = sqrt(n.val()) + 1e-6;
    mint s(sval);
    mc.reserve(sval);
    md.reserve(sval);
    mint invs = s.inv();
    static vector<size_t> st;
    st.resize(log2(sval) + 5);
    for (size_t i = sval; i > 1ull; i >>= 1ull) st[++pos] = i;
    mc.resize(2ull);
    md.resize(2ull);
    mc[0] = 1ull;
    mc[1] = s + 1ull;
    for (size_t l = st[pos]; pos; l = st[--pos]) {
        LagrangeInterpolation_ex(l >> 1ull, mint((l >> 1ull) + 1ull), mc, md);
        mc.resize(mc.size() << 1ull);
        std::copy(md.begin(), md.end(), mc.begin() + md.size());
        LagrangeInterpolation_ex(mc.size() - 1ull, invs * (l >> 1ull), mc, md);
        for (size_t i = 0ull, iend = mc.size(); i < iend; i++) mc[i] *= md[i];
        if (l & 1ull) for (size_t i = 0; i <= l; i++) mc[i] *= s * i + l;
        else mc.resize(l + 1ull);
    }
}
inline mint get_fac(unsigned long long v) {
    mint res(1);
    unsigned long long iend = v / sval;
    for (unsigned long long i = 0ull; i < iend; i++) res *= mc[i];
    for (unsigned long long i = 1ull * iend * sval + 1ull, iendd = v; i <= iendd; i++) res *= i;
    return res;
}
int main() {
    prepare(mint(1000005));
    int T = 0;
    unsigned long long n, m;
    int opt;
    mint ans, tmp;
    cin >> T;
    while (T--) {
        cin >> n >> m >> opt;
        if (!opt) n = n + m - 1;
        if (n < m) {
            cout << '0' << '\n';
            continue;
        }
        ans = 1;
        for (unsigned long long i = n, iend = n - m + 1; i >= iend; i--) ans *= i;
        tmp = get_fac(m);
        cout << ans / tmp << '\n';
    }
    return 0;
}

成功把紫题做成黑题