题解：

Analysis

​ 将每个组分别视为一个整体，引入一个新概念：”环“。

​ 定义：现有 $n$ 个组，每个组的编号分别为 $a_1,a_2, ... ,a_n$ ，若以 $a_1$ 为起点进行试卷的寻找，恰经过 $n-1$ 个不同的组后找到了自己的试卷，则称这 $n$ 个组形成了一个长度为 $n$ 的“环”。例如： $1$ 组卷传给 $2$ 组， $2$ 组卷传给 $3$ 组， $3$ 组卷传给 $1$组，则这三个组形成一个长度为 $3$ 的环。

​ 将原力清理大师所在的组编号为 $1$ 号，其余组分别编号为 $2,3, ... ,n$ ，则可以按照 $1$ 号组所在“环”的长度进行分类，先求出每种情况发生的概率。要求出这种概率，这里使用古典概型，并需要先了解本题一大关键——错位排列。

​ 错位排列，通俗的说，就是对 $1$ 到 $n$ 重新编号，使得每个数字的新编号与旧编号不相同，满足条件的情况总数，就是 $n$ 的错位排列的数量（即错排数），这里将该结果记作 $A_n$ 。易知，这 $m$ 个组所有可能的排列数即为 $A_m$ 。

​ 设此时原力清理大师所在的“环”的长度为 $i$ ，则满足条件的排列数量为长度为 $i$ 的“环”的排列数乘以其余不在该环内的所有组的错排数 $A_m$ 。由此，我们需要求出任意 $1 \leq i \leq n$ 的 $A_i$ 。

​ 首先提出结论：

​ 证明如下：

​ 对于 $1,2, ... ,n$ ，假设对于任意 $1 \leq i \leq n$ ，第 $i$ 组的卷传给了第 $a_i$ 组，且 $i != a_i$ ，则对于第 $n$ 组，设其上家为第 $j$ 组，则 $j$ 共有 $n-1$ 种取值；对于每一种特定的取值，若 $j = a_i$ ，则共有 $A{n-2}$ 种排列方式，即除去第 $j,n$ 两组后，剩下的所有组错排总数；若 $j != a_i$ ，则由于第 $n$ 组的卷不能给第 $j$ 组，则可以把第 $n$ 组的卷子等效为第 $j$ 组的卷子，则原情况可等价为除去第 $n$ 组以外剩下的 $n-1$ 组进行错位排列，则总数显然为 $A{n-1}$ ；故可得上式。

​ 接下来求解长度为 $i$ 的“环”的排列数：

​ 从 $1$ 组开始，$1$ 组可以将卷子传给第 $2,3, ... , n$ 组种的任意一组，共有 $n-1$ 种选择；若第 $1$ 组将卷传给了第 $i$ 组，则此时第 $i$ 组还剩下 $n-2$ 个组可以传递，即还剩下 $n-2$ 种选择……直到最后一组，必须将卷传给第 $1$ 组，完成闭环。因此，根据乘法原理，所求总数即为 $(n-1)(n-2)(n-3)...[n-(i-1)]$ 。

​ 至此，大部分的求解工作基本都已完成！不过需要特别注意的是，当所有的 $n$ 个组共同形成闭环时，不需要乘以剩余组的错排数，毕竟一个组都没剩下，总不能乘以 $0$ 吧🤔。

​ 要通过这道题，还需要了解什么是逆元。逆元是一个相对概念，即我们说 $i$ 相对于模数 $Mod$ 的逆元为 $j$ ，而不会说 $i$ 的逆元为 $j$ 。逆元可以理解为广义的倒数：对于 $i$ 的倒数 $j$ ，有 $i * j = 1$ ；而对于 $i$ 关于 $Mod$ 的逆元 $j$ ，有 $i * j$ 。要求解 $i$ 关于 $Mod$ 的逆元 $j$ ，需要利用欧拉定理，即：

其中 $p$ 为质数，且 $a$ 不是 $p$ 的倍数。（证明详见 欧拉定理 & 费马小定理 - OI Wiki (oi-wiki.org)​ ）

由于一个一个乘以 $a$ 效率太低，故而此处需要结合快速幂算法辅助。

所谓快速幂，是利用了 $a^2b=(a * a)^b$ 这一性质，通过倍增的方式以 $O(logb)$ 的复杂度快速求解 $a^b$ 的算法。详见乘法逆元 - OI Wiki (oi-wiki.org)。

最后，在实现代码的过程中，记得时刻关注数字有没有爆 $long long$ 噢~

Code

#include<bits/stdc++.h>

using namespace std;



using ll=long long;

#define Mod 1000000007



ll Quick_Mi(ll a,ll b)

{

  ll res=1;

  while(b)

  {

​    if(b&1) res=res*a%Mod;

​    b/=2,a=a*a%Mod;

  }

  return res;

}



int main()

{

  ll n,m;

  cin>>n>>m;

  ll a[m],b[m];//a为错排数，b为m-1乘到m-i-1

  a[0]=0,a[1]=1;

  for(ll i=2;i<m;i++) a[i]=i*(a[i-2]+a[i-1])%Mod;

  b[0]=m-1;

  for(ll i=1;i<m;i++) b[i]=b[i-1]*(m-i-1)%Mod;

  ll res=0,inv=Quick_Mi(n,Mod-2),Inv=Quick_Mi(a[m-1],Mod-2);

  for(ll i=1;i<m-1;i++)

  {

​    ll temp1=b[i-1]*a[m-i-2]%Mod,temp2=(n*(n+1)%Mod*Quick_Mi(2,Mod-2)%Mod*(i+1)%Mod+Mod-n)%Mod*inv%Mod;

​    res=(res+temp1*temp2%Mod*Inv%Mod)%Mod;

  }

  res=(res+b[m-2]*(n*(n+1)%Mod*Quick_Mi(2,Mod-2)%Mod*m%Mod+Mod-n)%Mod*inv%Mod*Inv%Mod)%Mod;

  cout<<res;

  return 0;

}