Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define ar array
- const int mod = 1e9 + 7;
- int pre[5][5] = {
- {0, 2, 2, 2, 2},
- {0, 16, 16, 24, 24},
- {0, 288, 384, 480, 576},
- {0, 9216, 13824, 23040, 26112},
- {0, 460800, 829440, 1428480, 2088960}
- };
- int bp(int a, int b){
- int rr = 1;
- while(b){
- if(b&1) rr = rr * 1ll * a % mod;
- a = a * 1ll * a % mod, b >>= 1;
- } return rr;
- }
- signed main(){
- ios::sync_with_stdio(0); cin.tie(0);
- int n, m; cin>>n>>m;
- vector<int> a(m);
- for(int i=0;i<2*n;i++){
- a[i % m]++;
- }
- vector<int> dp(2 * n + 1);
- vector<int> f(2 * n + 1), inv(2 * n + 1);
- f[0] = inv[0] = 1;
- for(int i=1;i<=2 * n;i++){
- f[i] = f[i-1] * 1ll * i % mod;
- inv[i] = bp(f[i], mod - 2);
- }
- auto C = [&](int n, int k){
- return f[n] * 1ll * inv[k] % mod * inv[n - k] % mod;
- };
- reverse(a.begin(), a.end());
- dp[a[0]] = 1;
- int sum = a[0];
- for(int i=1;i<m;i++){
- vector<int> nw(2 * n + 1);
- for(int j=0;j<=a[i];j++){
- for(int l=j;l<=sum;l++){
- nw[l + a[i] - j * 2] = (nw[l + a[i] - 2 * j] + dp[l] * 1ll * f[j] % mod * C(a[i], j) % mod * C(l, j)) % mod;
- }
- } dp = nw;
- sum += a[i];
- }
- int res = dp[0];
- for(int i=0;i<n;i++) res = res * 2ll % mod;
- res = res * 1ll * f[n] % mod;
- cout<<res<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement