使用类似传统的错排公式 \(D(n) = (n - 1) \times (D(n - 1) + D(n - 2))\) 的推导过程。
首先，\(D_i\) 整体除了一个 \(n!\)，代表后 \(n\) 个球整体相同。
局面设定为求 \(D(i)\)，从 \(1 \sim i\) 中抽出一个数 \(a\)，它只能放在其他的位置上，假设它占据了另一个数 \(b\) 在 \(1 \sim i\) 的位置，假如 \(b\) 放在了 \(a\) 的位置上，那么等价于剩下的数瞎错排，也就是 \(D(i - 2)\)，由于 \(a\) 有 \(i-1\) 种放的方式，于是贡献为 \((i - 1) \times D(i - 2)\)。
假如 \(b\) 没有放到 \(a\) 的位置上，那么 \(b\) 不能去 \(a\) 的位置，不能去 \(b\) 的位置，一共有 \(i - 2\) 个位置能去，其余元素也都有 \(i - 2\) 个位置可以去，相当于隔离掉 \(a\)，其他数错排，贡献为 \((i - 1) \times D(i - 1)\)。
再加入 \(a\) 放到了后面 \(n\) 个数的时候的贡献，此时 \(a\) 有 \(n\) 个可以选择的方案，然后只用关心剩下 \(i - 1\) 个数错排，那么就是 \(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\)。
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
// 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！
// 没有力量的理想是戏言，没有理想的力量是空虚
#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;
}
} ;