直接上板子

const ll mod =(ll) 1e9+7;const int maxn = 2100001;ll f[maxn];int n;void init() {    f[0] = f[1] = 1;    for(int i = 2; i < maxn; i++) f[i] = (f[i-1] * i) % mod;}ll mul(ll x, ll n) {    ll ret = 1;    while(n) {        if(n & 1) ret = (ret * x) % mod;        n >>= 1;        x = (x * x) % mod;    }    return ret;}ll exgcd(ll a, ll b, ll &x, ll &y) {    if(b == 0) {        x = 1;        y = 0;        return a;    }    else {        ll ret = exgcd(b, a%b, x, y);        ll tmp = x;        x = y;        y = tmp - a / b * y;        return ret;    }}ll inv(ll a) {    ll x, y;    exgcd(a, mod, x, y);    return (x % mod + mod) % mod;}ll C(ll x, ll y) {    return f[x] * inv(f[x-y]) % mod * inv(f[y]) % mod;}ll Catalan(int n) {    return C(2*n, n) * inv(n+1) % mod;}ll s[maxn][maxn];void init2() {    mem0(s);    s[1][1] = 1;    for( int i = 2; i <= maxn-1; i++ ) {        for( int j = 1; j <= i; j++ ) {            s[i][j] = s[i-1][j-1]+j*s[i-1][j];            if( s[i][j] >= mod ) s[i][j] %= mod;        }    }}ll S(int n, int m) {    return f[m]*s[n][m]%mod;}