思路：

　　首先，要确定定m个位置，这些位置要求必须i=a[i]，所以方案数是C(n,m)，对于剩下的位置，要求i!=a[i]，所以要求是一个错排。

：

p[0] = 0,p[1] = 1

p[i] = （i-1）*（p[i-1]+p[i-2]）

 

代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6  7 using namespace std; 8  9 const int mod = 1e9+7;10 11 int f[1000100],p[1000100];12 13 inline int read() {14     int x = 0,f = 1;char ch=getchar();15     for (; ch<'0'||ch>'9'; ch=getchar()) if(ch=='-')f=-1;16     for (; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';17     return x*f;18 }19 20 void init() {21     f[0] = 1;22     for (int i=1; i<=1000000; ++i) f[i] = (1ll * f[i-1] * i) % mod;23     p[1] = 0;p[2] = 1;24     for (int i=3; i<=1000000; ++i) p[i] = (1ll * (i-1) * (p[i-1] + p[i-2])) % mod;25 }26 27 int inv(int a,int b) {28     int ans = 1;29     while (b) {30         if (b & 1) ans = (1ll*ans*a) % mod;31         a = (1ll * a * a) % mod;32         b >>= 1;33     }34     return ans % mod;35 }36 37 void solve(int n,int m) {38     if (n == m) {cout << "1\n";return ;}39     int t1 = inv(f[m],mod-2),t2 = inv(f[n-m],mod-2);40     int ans = (1ll * f[n] * t1) % mod;41     ans = (1ll * ans * t2) % mod;42     ans = (1ll * ans * p[n-m]) % mod;43     cout << ans << "\n";44 }45 46 int main() {47     int T = read();48     init();49     while (T--) {50         int n = read(),m = read();51         solve(n,m);52     }53     return 0;54 }