Farmer John 有 $N$ $(1 \le N \le 3000)$ 头大小各异的奶牛。他最初为每头奶牛建造了一个个性化的牛棚，但现在一些奶牛已经长得比它们的牛棚大了。具体来说，FJ 最初建造了 $N$ 个大小分别为 $t_1, t_2, \ldots, t_N$ 的牛棚，而奶牛现在的大小分别为 $s_1, s_2, \ldots, s_N$ ($1 \le s_i, t_i \le 10^9$)。

每天晚上，奶牛们都会进行寻找牛棚睡觉的仪式。奶牛 $i$ 可以睡在牛棚 $j$ 中，当且仅当它能装进该牛棚（即 $s_i \le t_j$）。每个牛棚最多只能容纳一头奶牛。

如果一个奶牛到牛棚的匹配满足以下条件，我们称其为极大匹配：每一头分配到牛棚的奶牛都能装进该牛棚，且每一头未分配的奶牛都无法装进匹配中剩余的任何空牛棚。

计算极大匹配的数量，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $s_1, s_2, \ldots, s_N$。

第三行包含 $N$ 个空格分隔的整数 $t_1, t_2, \ldots, 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 \le 8$。
• 测试点 4-12 中，$N \le 50$。
• 测试点 13-20 中，无额外限制。

题目来源：Nick Wu