题目描述

在数轴上有 $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

输入

2 2
2 3
1 4

输出

3

样例 2

输入

3 4
2 5 10
1 3 7 13

输出

8

样例 3

输入

4 1
1 2 4 5
3

输出

1

样例 4

输入

4 5
2 5 7 11
1 3 6 9 13

输出

6

样例 5

输入

10 10
4 13 15 18 19 20 21 22 25 27
1 5 11 12 14 16 23 26 29 30

输出

22

说明/提示

限制条件

• $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 翻译