样例下载

题目描述

Alice 和 Bob 正在玩一个游戏。

有两堆各 N 个小球，每个小球上均写有一个号码。

第一堆小球写着的号码分别为 $A_1, A_2, ……, A_N$;

第二堆小球写着的号码分别为 $B_1, B_2, ……, B_N$。

现在让 Alice 和 Bob 开始取球。

每人每次需要从两堆各取一个小球，要求第一堆所取小球的号码不能大于第二堆所取小球的号码。

游戏由 Alice 开始。他可以自己取任意次（可以为 0 次），然后再让 Bob 开始取球。

Alice 希望自己结束取球后，Bob 第一次取球便一个球也无法取走。

问：Alice 有多少种取球方案？答案可能很大，你需要将其 mod $(10^9+7)$ 后输出。

两种取球方案不同，当且仅当满足以下条件之一：

（1）取球次数不同；

（2）一种方案中某一次取走的两个小球在另一种方案中没有被同时取走。

输入格式

第一行：一个整数 $N$。

第二行：$N$ 个整数 $A_i$。

第三行：$N$ 个整数 $B_i$。

输出格式

一个整数，表示答案 mod $(10^9+7)$。

样例1输入

3
4 5 6
1 2 3

样例1输出

1

样例1解释

Alice 选择取 0 次，即不取，也算一种方案。

样例2输入

3
1 2 1
1 2 3

样例2输出

6

样例2解释

6 种方案如下，其中用橙色连线表示某次取走的两个小球。

数据范围

• 10% 的数据：$N ≤ 10$。
• 40% 的数据：$N ≤ 50$。
• 100% 的数据：$1 ≤ N ≤ 5000$, $1 ≤ A_i,B_i ≤ 10^9$