题解

1.$m$的排列在一个$n$的排列中： 共计有 $m!(n−m+1)!$ 种可能。

2.$m$的排列在连续的两个$n$排列中 假设排列为：
$\{ p_1, p_2, \dots, p_{k-1}, p_k, p_{k+1}, \dots, p_j, \dots, p_n \}$，其中满足 $p_k < p_{k+1}$，且序列 $[k+1, n]$ 为降序。
此时，排列的后继为：
$\{ p_1, p_2, \dots, p_{k-1}, p_j, p_n, p_{n-1}, \dots, p_{j+1}, p_k, p_{j-1}, \dots, p_{k+1} \}$ 不难发现，排列的后继是通过翻转降序段，并交换前一个数 $k$ 与降序段中最右侧大于 $k$ 的数得到的。

假设 $m$ 的排列起始点为 $i$，我们根据 $k$ 的位置进行分类讨论：

2.1 $i \leq k$ 且 $i + m - 1 > n$

前一个排列在区间 $[i, n-1]$ 中存在，必须存在 $j$ 使得 $p_j < p_{j+1}$。 排列的数量为：

$(n - m)! \cdot \left[ m! - C_{m}^{n-i+1} \cdot (m - (n - i + 1))! \right]$

2.2 $i > k$ 且 $n < i + m - 1 < j + n$

易证不存在 $i+m-1 \geq j$ 的情况。 区间 $[n - m, n]$ 中的排列数为 $(n - m)! - 1$。 剩余 $m$ 个数在后一个 $n$ 排列中为 $[m - (n - i + 1)]!$，总排列数为：

$C_{m}^{n - i + 1} \cdot [m - (n - i + 1)]!$

最终的排列数为：

$\left[ (n - m)! - 1 \right] \cdot C_{m}^{n - i + 1} \cdot [m - (n - i + 1)]!$

将三者相加即可得到最终的排列数量。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
using PII=std::pair<int,int>;
using i64=long long;
template<class T>
constexpr T power(T a,i64 b) {
    T res=1;
    for(;b;b/=2,a*=a){
        if(b%2)res*=a;
    }
    return res;
}

constexpr i64 mul(i64 a,i64 b,i64 p){
    i64 res=a*b-i64(1.L*a*b/p)*p;
    res%=p;
    if(res<0)res+=p;
    return res;
}

template<i64 P>
struct MLong{
    i64 x;
    constexpr MLong():x{}{}
    constexpr MLong(i64 x):x{norm(x % getMod())}{}
    
    static i64 Mod;
    constexpr static i64 getMod(){
        if(P>0)return P;
        else return Mod;
    }
    constexpr static void setMod(i64 Mod_){
        Mod=Mod_;
    }
    constexpr i64 norm(i64 x)const{
        if(x<0)x+=getMod();
        if(x>=getMod())x-=getMod();
        return x;
    }
    constexpr i64 val()const{
        return x;
    }
    explicit constexpr operator i64() const{
        return x;
    }
    constexpr MLong operator-() const{
        MLong res;
        res.x=norm(getMod()-x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x!=0);
        return power(*this,getMod()-2);
    }
    constexpr MLong &operator*=(MLong rhs)&{
        x=mul(x,rhs.x,getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs)&{
        x=norm(x+rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs)&{
        x=norm(x-rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs)&{
        return *this*=rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs,MLong rhs){
        MLong res=lhs;
        res*=rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs,MLong rhs){
        MLong res=lhs;
        res+=rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs,MLong rhs){
        MLong res=lhs;
        res-=rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs){
        MLong res=lhs;
        res/=rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is,MLong &a){
        i64 v;
        is>>v;
        a=MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os,const MLong &a){
        return os<<a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs){
        return lhs.val()==rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs){
        return lhs.val()!=rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod=i64(1E18)+9;

template<int P>
struct MInt{
    int x;
    constexpr MInt():x{}{}
    constexpr MInt(i64 x):x{norm(x % getMod())}{}
    
    static int Mod;
    constexpr static int getMod(){
        if(P>0)return P;
        else return Mod;
    }
    constexpr static void setMod(int Mod_){
        Mod=Mod_;
    }
    constexpr int norm(int x)const{
        if(x<0)x+=getMod();
        if(x>=getMod())x-=getMod();
        return x;
    }
    constexpr int val()const{
        return x;
    }
    explicit constexpr operator int() const{
        return x;
    }
    constexpr MInt operator-() const{
        MInt res;
        res.x=norm(getMod()-x);
        return res;
    }
    constexpr MInt inv() const{
        assert(x!=0);
        return power(*this,getMod()-2);
    }
    constexpr MInt &operator*=(MInt rhs)&{
        x=1LL*x*rhs.x%getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs)&{
        x=norm(x+rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs)&{
        x=norm(x-rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs)&{
        return *this*=rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs,MInt rhs){
        MInt res=lhs;
        res*=rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs,MInt rhs){
        MInt res=lhs;
        res+=rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs,MInt rhs){
        MInt res=lhs;
        res-=rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs,MInt rhs){
        MInt res=lhs;
        res/=rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is,MInt &a){
        i64 v;
        is>>v;
        a=MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os,const MInt &a){
        return os<<a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs){
        return lhs.val()==rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs){
        return lhs.val()!=rhs.val();
    }
};

template<>
int MInt<0>::Mod=998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P=1e9+7;
using Z=MLong<P>;
struct Comb{
    int n;
    vector<Z> _fac,_inv;
 
    Comb():_fac{1},_inv{0}{}
    Comb(int n):Comb(){init(n);}
    void init(int m){
        if(m<=n)return;
        _fac.resize(m+1);_inv.resize(m+1);
        for(int i=n+1;i<=m;i++)_fac[i]=_fac[i-1]*i;
        _inv[m]=_fac[m].inv();
        for(int i=m;i>n;i--)_inv[i-1]=_inv[i]*i;
        n=m;
    }
    Z fac(int x){
        if(x>n)init(x);
        return _fac[x];
    }
    Z inv(int x){
        if(x>n)init(x);
        return _inv[x];
    }
    Z C(int x,int y) {
        if(x<0||y<0||x<y)return 0;
        return fac(x)*inv(y)*inv(x-y);
    }
    Z P(int x,int y) {
        if(x<0||y<0||x<y)return 0;
        return fac(x)*inv(x-y);
    }
}comb(1<<21);
std::vector<Z> sum(1e6,0);
void init(){
	for(int i=1;i<1e6;i++)sum[i]=comb.inv(i);
	for(int i=1;i<1e6;i++)sum[i]+=sum[i-1];
}
void solve(){
	int n,m;std::cin>>n>>m;
	Z ans=comb.fac(m)*comb.fac(n-m+1);
	ans+=(Z)(m-1)*comb.fac(m)*comb.fac(n-m)-comb.fac(m)*sum[m-1];
	std::cout<<ans<<'\n';
}
signed main(){
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(10);
	init();
	int T=1;
	std::cin>>T;
	while(T--)solve();
	return 0;
}