Description：

$N\times M$ 的棋盘，每列最多放一个棋子，每行前 $left[i]$ 个格子恰好有一枚棋子，每行后 $right[i]$ 个格子恰好有一枚棋子，问方案数。

$1\le N\le 50,1\le M \le 200$

Solution：

因为每列最多放一枚棋子，所以一般是以列为阶段划分状态，设 $f[i][j][k]$ 表示做到了第 $i$ 列，已经放了 $j$ 枚棋子，还有 $k$ 个右区间没放。然后到每一个列时，如果有 $l$ 个左区间到这里截止，那么就为这 $l$ 个左区间分配棋子，对于当前这一列，可以满足一个左区间，满足一个右区间，放在一个空白区域和不放，这里不放的含义并不是真的不放，而是等以后有左区间时再考虑这一列的摆放，设有 $l$ 个左区间从这里开始， $r$ 同理，如果满足左区间，那么就强制把一个棋子放在左区间，再在 $i-j$ 个棋子中选 $l-1$ 个，注意这里行交换后是另一种状态，所以应该是乘一个排列数，还应再乘 $l$ ，代表这一列有 $l$ 个可以选。如果满足右区间，就在 $i-j$ 个棋子里选 $l$ 个，并且 $k'=k+r-1$ ，排列数可以预处理阶乘及阶乘逆元求。如果放在中间位置，那么还是 $P_{i-j}^l$ ，右边 $k'=k+r$ ， $j'=j+1$ ，不放和放在中间只有 $j'=j$ 的差距。在最后把所有棋子个数的答案累加。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,m;

#define MAXN 51

#define MAXM 201

ll lef[MAXN],rig[MAXN];

ll f[MAXM][MAXM][MAXN];

ll fac[MAXM],inv[MAXM];

#define MOD 1000000007

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll P(ll n,ll m)

{

	if(n < 0 || m < 0)return 0ll;

	if(m > n)return 0ll;

	return fac[n] * inv[n - m] % MOD;

}

int main()

{

	scanf("%lld%lld",&n,&m);

	for(ll i = 1;i <= n;++i)scanf("%lld%lld",&lef[i],&rig[i]);

	fac[0] = 1;

	for(ll i = 1;i <= m;++i)fac[i] = fac[i - 1] * i % MOD;

	inv[m] = power(fac[m],MOD - 2);

	for(ll i = m - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % MOD;

	f[0][0][0] = 1;

	for(ll i = 1;i <= m;++i)

	{

		ll l = 0,r = 0,b = 0;

		for(ll j = 1;j <= n;++j)

		{

			if(lef[j] == i)++l;

			if(m - rig[j] + 1 == i)++r;

			if(lef[j] < i && m - rig[j] + 1 > i)++b;

		}

		for(ll j = 0;j < i;++j)

		{

			for(ll k = 0;k <= n;++k)

			{

				f[i][j + l][k + r] = (f[i][j + l][k + r] + f[i - 1][j][k] * P((i - 1) - j,l - 1) % MOD * l % MOD) % MOD;

				f[i][j + l + 1][k + r - 1] = (f[i][j + l + 1][k + r - 1] + f[i - 1][j][k] * P((i - 1) - j,l) % MOD * (k + r) % MOD) % MOD;

				f[i][j + l + 1][k + r] = (f[i][j + l + 1][k + r] + f[i - 1][j][k] * P((i - 1) - j,l) % MOD * b % MOD) % MOD;

				f[i][j + l][k + r] = (f[i][j + l][k + r] + f[i - 1][j][k] * P((i - 1) - j,l) % MOD) % MOD;

			}

		}

	}

	ll ans = 0;

	for(int i = 0;i <= m;++i)ans = (ans + f[m][i][0]) % MOD;

	cout << ans << endl;

	return 0;

}