solution

首先单独考虑蓝色和红色的染色方式。

如果只染蓝色（红色）和绿色，我们枚举一个蓝色边的数量x,然后方案数就是。所以总的方案数就是。

然后容斥合并蓝色和红色的方案。枚举蓝色和红色边重复的数量x,那么答案就是。所以最终答案就是

注意到上面求单个的过程是的。预处理f数组的复杂度就是。所以考虑用更优秀的方法求f。

将f打表如下:

找规律或OEIS发现递推式:。然后就可以线性预处理了。

总复杂度

code

/*
* @Author: wxyww
* @Date: 2020-04-09 15:26:44
* @Last Modified time: 2020-04-09 19:30:33
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 10000004,mod = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int jc[N],inv[N],f[N];
ll qm(ll x,ll y) {
    ll ret = 1;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) ret = ret * x % mod;
    return ret;
}
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;
}
void solve(int n) {
    ll ans = 0;
    for(int i = 0;i <= n;++i) 
        ans += C(n,i) * A(n,i);
    cout<<ans<<endl;
}
int main() {
    int n = read();
    jc[0] = 1;
    for(int i = 1;i <= n;++i)
        jc[i] = 1ll * jc[i - 1] * i % mod;
    inv[n] = qm(jc[n],mod - 2);



    for(int i = n - 1;i >= 0;--i)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    // for(int i = 1;i <= n;++i) {
    //     solve(i);
    // }
    // return 0;

    f[0] = 1;f[1] = 2;
    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;

    // cout<<A(n,0)<<endl;
    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;
}