记录编号	577714	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO20Dec Platinum]Sleeping Cows	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2022-11-22 14:54:07	内存使用	0.00 MiB

// Problem: P7154 [USACO20DEC] Sleeping Cows P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7154
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using i64 = long long;

const int maxn = 3e3 + 5;
const i64 mod = 1e9 + 7;
int s[maxn],t[maxn],n,a[maxn],b[maxn];
i64 f[maxn][maxn],g[maxn][maxn],frac[maxn];

int main() {
	freopen("usaco_20Dec_sleep.in","r",stdin);
	freopen("usaco_20Dec_sleep.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&s[i]);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&t[i]);
	std::sort(s + 1 , s + 1 + n);
	std::sort(t + 1 , t + 1 + n);
	for(int i = 1,r = 1;i <= n;++ i) {
		for(;r <= n&&t[r] < s[i];++ r);
		a[i] = r;
	}
	for(int i = 1,l = 0;i <= n;++ i) {
		for(;l < n&&s[l + 1] <= t[i];++ l);
		b[i] = l;
	}
	frac[0] = 1;
	for(int i = 1;i <= n;++ i)
		frac[i] = 1ll * i * frac[i - 1] % mod;
	f[0][0] = 1;
	for(int i = 1;i <= n;++ i) {
		f[i][0] = 1;
		for(int k = 1;k <= i;++ k) {
			f[i][k] = (f[i - 1][k] + f[i - 1][k - 1] * std::max(b[i] - k + 1 , 0)) % mod;
		}
	}
	g[n + 1][0] = 1;
	for(int i = n;i;-- i) {
		g[i][0] = 1;
		for(int k = 1;k <= n - i + 1;++ k) {
			g[i][k] = (g[i + 1][k] + 1ll * g[i + 1][k - 1] * std::max(n - a[i] - k + 2 , 0)) % mod;
		}
	}
	i64 ans = f[n][n];
	for(int i = 1;i <= n;++ i) {
		for(int j = 0;j < i&&j <= n - a[i] + 1;++ j) {
			(ans += 1ll * g[i + 1][n - a[i] + 1 - j] * f[a[i] - 1][i - j - 1] % mod * frac[j] % mod) %= mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}