AT_arc101_d [ARC101F] Robots and Exits

在数轴上有 $N$ 个机器人和 $M$ 个出口。这 $N+M$ 个坐标都是整数且互不相同。对于每个 $i$（$1 \leq i \leq N$），从左到右第 $i$ 个机器人的坐标为 $x_i$。对于每个 $j$（$1 \leq j \leq M$），从左到右第 $j$ 个出口的坐标为 $y_j$。 Sunuque 君可以以任意顺序重复以下两种操作，使所有机器人同时移动： - 使数轴上所有机器人的坐标都减 $1$。 - 使数轴上所有机器人的坐标都加 $1$。 每当某个机器人与某个出口重合时，该机器人就会通过该出口并从数轴上消失。Sunuque 君会不断操作，直到所有机器人都消失。 所有机器人消失后，每个机器人通过哪个出口的组合有多少种可能？请输出对 $10^9+7$ 取模的结果。 如果存在某两个组合，使得至少有一个机器人通过的出口不同，则认为这两个组合是不同的。

输入按以下格式从标准输入读入。 > $N$ $M$ $x_1$ $x_2$ $\ldots$ $x_N$ $y_1$ $y_2$ $\ldots$ $y_M$

输出所有机器人消失后，每个机器人通过哪个出口的组合数，对 $10^9+7$ 取模。

## 限制条件 - $1 \leq N, M \leq 10^5$ - $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^9$ - $1 \leq y_1 < y_2 < \ldots < y_M \leq 10^9$ - 给定的所有坐标均为整数。 - 给定的所有坐标互不相同。 ## 样例解释 1 从左到右第 $i$ 个机器人称为机器人 $i$，从左到右第 $j$ 个出口称为出口 $j$。$(\text{机器人 }1\text{ 通过的出口}, \text{机器人 }2\text{ 通过的出口})$ 的可能组合有以下 $3$ 种： - $(\text{出口 }1, \text{出口 }1)$ - $(\text{出口 }1, \text{出口 }2)$ - $(\text{出口 }2, \text{出口 }2)$ ## 样例解释 2 每个机器人可以独立选择通过哪个出口，因此组合数为 $2^3 = 8$ 种。 ## 样例解释 3 所有机器人都只能通过出口 $1$。 由 ChatGPT 4.1 翻译