分数: 900 点
问题陈述
有 N 机器人和 M 在数轴上存在。 的 N + M 这些坐标都是整数并且都是不同的。 对于每个 i (1 \leq i \leq N),坐标 i左起第一个机器人是 x_i。 另外,对于每个 j (1 \leq j \leq M),坐标 j左边第一个出口是 y_j.
Snuke可以按任意顺序重复执行以下两种操作,以同时移动所有机器人:
- 将数轴上所有机器人的坐标增加 1.
- 将数轴上所有机器人的坐标递减 1.
当每个机器人的位置与出口重合并穿过该出口时,每个机器人都会从数轴上消失。 Snuke将继续执行操作,直到所有机器人消失。
当所有机器人消失后,机器人可以使用多少种出口组合? 求计数模数 10^9 + 7。 这里,当存在机器人在这两个组合中使用不同的出口时,这两个出口组合被认为是不同的。
约束
- 1 \leq N, M \leq 10^5
- 1 \leq x_1 < x_2 < ... < x_N \leq 10^9
- 1 \leq y_1 < y_2 < ... < y_M \leq 10^9
- 所有给定的坐标都是整数。
- 所有给定的坐标都是不同的。
输入
输入由标准输入按以下格式给出:
N M x_1 x_2 ... x_N y_1 y_2 ... y_M
输出
打印所有机器人消失时机器人可以使用的出口组合数量,取模 10^9 + 7.
示例输入 1
2 2 2 3 1 4
示例输出 1
3
的 i左边第一个机器人将被称为机器人 i,以及 j左边第一个出口将被称为 Exit j。 出口有三种可能的组合(机器人使用的出口 1,机器人使用的出口 2)如下:
- (退出 1, 退出 1)
- (退出 1, 退出 2)
- (退出 2, 退出 2)
示例输入 2
3 4 2 5 10 1 3 7 13
示例输出 2
8
每个机器人的出口可以独立选择,因此有 2^3 = 8 可能的退出组合。
示例输入 3
4 1 1 2 4 5 3
示例输出 3
1
每个机器人都使用 Exit 1.
示例输入 4
4 5 2 5 7 11 1 3 6 9 13
示例输出 4
6
示例输入 5
10 10 4 13 15 18 19 20 21 22 25 27 1 5 11 12 14 16 23 26 29 30
示例输出 5
22