DerangementsDiv2

srm717div2hard.cpp

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

struct DerangementsDiv2 {
    long long bin_pow_mod(long long x,long long y) {
        if(x==0) return 0;
        long long prod=1;
        while(y>0) {
            if(y&1) {
                prod=(prod*x)%MOD;
            }
            x=(x*x)%MOD;
            y>>=1;
        }
        return prod%MOD;
    }
    int count(int n, int m) {
        vector<long long> fact(200),fact_inv(200);
        fact[0]=fact_inv[0]=1;
        for(int i=1;i<200;i++) {
            fact[i]=(fact[i-1]*i)%MOD;
            fact_inv[i]=bin_pow_mod(fact[i],MOD-2);
        }
        auto nCr=[&](int n,int r) {
            return ((fact[n]*fact_inv[r])%MOD*fact_inv[n-r])%MOD;
        };

        int neg=0;
        for(int i=1;i<=m;i++) {
            if(i%2==1) {
                neg+=(nCr(m,i)*fact[n+m-i])%MOD;
            } else {
                neg-=(nCr(m,i)*fact[n+m-i])%MOD;
            }
            neg%=MOD;
        }
        return (fact[n+m]-neg+MOD)%MOD;
    }
};