根据楚巨的描述，这个题目有亿点点难……

题目传送

Solution

根据二分图的解题套路，可以转换为一个n * n的矩阵中去进行处理，又因为题目给了边的特性，我们假设xi，yi填上红色就是xi，yi的边涂成红色（因为绿色的没啥特性，所以可以不管这种颜色），两红边（蓝边类似）不能共享端点，也就是说在n * n的矩阵中，任意的一行或一列不能有相同颜色的点。
1、只填红色或者蓝色，显然有f[n] = 种方案。（n行里面取若干行，没有次序之分，再取若干列，这时候2 1和1 2,存在差别，所以要使用全排列）。
2、红蓝都有，我们枚举红蓝重复的边数x，根据容斥的思想那么答案就是 ,最终求和得到答案等于

3、分析时间复杂度的时候发现预处理阶乘和逆元都可以通过O(n)搞定，不过按照我们上面的组合数×全排列的
方法时间复杂度是O( )，n是1e7，TLE妥妥的。那我们怎么办呢？ 欸嘿嘿打表 2，7，34，209，1546，13327，130922……再根据一个神奇的网站OEIS，一找，果然有递推关系。
f[x]=2 * x * f[x-1]-f[x-2] *

注意存在减法！！取模需谨慎，还有阶乘，ll开起来，（虽然我没开 =_= ）.

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e7 + 5;
const int MOD = 1e9 + 7;
int jc[N], inv[N], f[N];

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)    ans = ans * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}

void init(int n) { //预处理阶乘数组和逆元，求解组合数
    jc[0] = 1;
    for (int i = 1; i <= n; ++i)
        jc[i] = 1ll * jc[i - 1] * i % MOD;
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    f[0] = 1; f[1] = 2; //线性递推f数组
    for (int i = 2; i <= n; ++i) {
        f[i] = (2ll * i * f[i - 1] - 1ll * f[i - 2] * (i - 1) % MOD * (i - 1) % MOD) % MOD;
        (f[i] += MOD) %= MOD; //保证正数
    }
}

ll C(int n, int m) {
    return 1ll * jc[n] * inv[m] % MOD * inv[n - m] % MOD;
}

ll A(int n, int m) {
    return 1ll * jc[n] * inv[n - m] % MOD;
}

int main() {
    int n = read();
    init(n);
    ll ans = 0;
    for (int i = 0; i <= n; ++i) {
        ll k = 1;
        if (i & 1) k = -1;
        ans += k * C(n, i) * A(n, i) % MOD * f[n - i] % MOD * f[n - i] % MOD;
        ans %= MOD;
    }
    printf("%lld\n", (ans + MOD) % MOD);
    return 0;
}