使用類似傳統(tǒng)的錯排公式 \(D(n) = (n - 1) \times (D(n - 1) + D(n - 2))\) 的推導(dǎo)過程。

首先，\(D_i\) 整體除了一個 \(n!\)，代表后 \(n\) 個球整體相同。

局面設(shè)定為求 \(D(i)\)，從 \(1 \sim i\) 中抽出一個數(shù) \(a\)，它只能放在其他的位置上，假設(shè)它占據(jù)了另一個數(shù) \(b\) 在 \(1 \sim i\) 的位置，假如 \(b\) 放在了 \(a\) 的位置上，那么等價于剩下的數(shù)瞎錯排，也就是 \(D(i - 2)\)，由于 \(a\) 有 \(i-1\) 種放的方式，于是貢獻(xiàn)為 \((i - 1) \times D(i - 2)\)。

假如 \(b\) 沒有放到 \(a\) 的位置上，那么 \(b\) 不能去 \(a\) 的位置，不能去 \(b\) 的位置，一共有 \(i - 2\) 個位置能去，其余元素也都有 \(i - 2\) 個位置可以去，相當(dāng)于隔離掉 \(a\)，其他數(shù)錯排，貢獻(xiàn)為 \((i - 1) \times D(i - 1)\)。

再加入 \(a\) 放到了后面 \(n\) 個數(shù)的時候的貢獻(xiàn)，此時 \(a\) 有 \(n\) 個可以選擇的方案，然后只用關(guān)心剩下 \(i - 1\) 個數(shù)錯排，那么就是 \(n \times D(i - 1)\)。

于是 \(D(i) = (n + i- 1) \times D(i - 1) + (i - 1) \times D(i - 2)\)。

其中 \(D(0) = 0, D(1) = n\)。

// 德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛
// 德麗莎的可愛在于德麗莎很可愛，德麗莎為什么很可愛呢，這是因?yàn)榈蔓惿芸蓯郏?// 沒有力量的理想是戲言，沒有理想的力量是空虛
#include <bits/stdc++.h>
#define LL long long
using namespace std;
namespace IO {
  const int SZ = (1 << 21) + 1;
  char ib[SZ], *iS, *iT, ob[SZ], *oS = ob, *oT = oS + SZ - 1, cc, qu[55]; int ff, qr;
  #define gc() (iS == iT ? (iT = (iS = ib) + fread(ib, 1, SZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
  void flush() { fwrite(ob, 1, oS - ob, stdout), oS = ob; }
  void putc(char x) { *oS++ = x; if (oS == oT) flush(); }
  template <class I>
  void read(I &x) {
    for (ff = 1, cc = gc(); cc < '0' || cc > '9'; cc = gc()) if (cc == '-')  ff = -1;
    for (x = 0; cc <= '9' && cc >= '0'; cc = gc())  x = x * 10 + (cc & 15);
    x *= ff;
  }
  template <class I, class... Y>
  void read(I &t, Y &... a) {  read(t), read(a...);  }
  template <class I>
  void write(I x) {
    if (!x)  putc('0');
    if (x < 0) putc('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putc(qu[qr --]);
  }
} using namespace IO;
template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define repd(i, l, r) for (int i = (l); i >= (r); i--)
#define REP(i, l, r)  for (int i = (l); i < (r); i++)
const int N = 2e6, mod = 1e9 + 7;
LL f[N];
class DerangementsStrikeBack {
  public:
  int count(int n,int m) {
    f[0] = 1, f[1] = n;
    rep (i, 2, m)  f[i] = (1ll * f[i - 1] * (n + i - 1) % mod + 1ll * f[i - 2] * (i - 1) % mod) % mod;
    int ans = 0;
    rep (i, 1, m)  ans ^= f[i];
    return ans;
  }
} ;