[USACO20DEC] Sleeping Cows P

题目描述

Farmer John 有 $N$($1≤N≤3000$)头各种大小的奶牛。他原本为每头奶牛量身定制了牛棚,但现在某些奶牛长大了,使得原先的牛棚大小不够用。具体地说,FJ 原来建造了 $N$ 个牛棚的大小为 $t_1,t_2,…,t_N$,现在奶牛的大小为 $s_1,s_2,…,s_N$($1≤s_i,t_i≤10^9$)。 每天晚上,奶牛们都会按照某种方式寻找睡觉的牛棚。奶牛 $i$ 可以睡在牛棚 $j$ 中当且仅当她的大小可以进入牛棚($s_i≤t_j$)。每个牛棚中至多可以睡一头奶牛。 我们称奶牛与牛棚的一个匹配是极大的,当且仅当每头奶牛可以进入分配给她的牛棚,且对于每头未被分配牛棚的奶牛无法进入任何未分配的空牛棚。 计算极大的匹配的数量模 $10^9+7$ 的结果。

输入输出格式

输入格式


输入的第一行包含 $N$。 第二行包含 $N$ 个空格分隔的整数 $s_1,s_2,…,s_N$。 第三行包含 $N$ 个空格分隔的整数 $t_1,t_2,…,t_N$。

输出格式


输出极大的匹配的数量模 $10^9+7$ 的结果。

输入输出样例

输入样例 #1

4
1 2 3 4
1 2 2 3

输出样例 #1

9

说明

以下是全部九种极大的匹配。有序对 $(i,j)$ 表示奶牛 $i$ 被分配到了牛棚 $j$。 ``` (1, 1), (2, 2), (3, 4) (1, 1), (2, 3), (3, 4) (1, 1), (2, 4) (1, 2), (2, 3), (3, 4) (1, 2), (2, 4) (1, 3), (2, 2), (3, 4) (1, 3), (2, 4) (1, 4), (2, 2) (1, 4), (2, 3) ``` - 测试点 2-3 中,$N≤8$。 - 测试点 4-12 中,$N≤50$。 - 测试点 13-20 没有额外限制。 供题:Nick Wu