← 返回题目列表

AtCoder · arc101_d

F. 机器人和出口

中文机器翻译题面 查看原题

分数: 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