# CCA的小球

## 代码

```#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

int n, a[1000001];
int two;
ll ans, two_times[1000001], inv[1000001], fac[1000001], zf = 1;

ll ksm(ll x, ll y) {//用来算逆元的
ll re = 1;
while (y) {
if (y & 1) re = (re * x) % mo;
x = (x * x) % mo;
y >>= 1;
}
return re;
}

void init() {//预处理
two_times[0] = inv[0] = fac[0] = 1;
for (int i = 1; i <= 1000000; i++) two_times[i] = (two_times[i - 1] * 2) % mo;
for (int i = 1; i <= 1000000; i++) fac[i] = (fac[i - 1] * i) % mo;
inv[1000000] = ksm(fac[1000000], mo - 2);
for (int i = 1000000 - 1; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mo;
}

int main() {
init();

scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}

sort(a + 1, a + n + 1);

for (int i = 2; i <= n; i++)
if (a[i] == a[i - 1]) {
two++;
}

for (int i = 0; i <= two; i++) {//根据式子容斥
ans = (ans + zf * (fac[two] * inv[i] % mo * inv[two - i] % mo * fac[n - i] % mo * ksm(two_times[two - i], mo - 2)) % mo) % mo;
if (ans < 0) ans += mo;
zf = -zf;
}

printf("%lld", ans);

return 0;
}```