题目描述

小 S 负责维护一条自动分拣带。分拣带可以看作一条数轴，分拣带上有 $N$ 个包裹与$M$ 个分拣口。所有包裹和分拣口所在的位置均为整数且互不相同。对于每个 $i$（$1 \le i \le N$），从左到右第 $i$ 个包裹的位置为 $p_i$。对于每个 $j$（$1 \le j \le M$），从左到右第 $j$ 个分拣口的位置为 $q_j$。

小 S 可以以任意顺序重复以下两种操作：

• 使所有尚未被分拣的包裹的位置都减 $1$；
• 使所有尚未被分拣的包裹的位置都加 $1$。

每当某个包裹与某个分拣口位于同一位置时，该包裹会立刻进入这个分拣口，并从分拣带上消失。小 S 会不断操作，直到所有包裹都被分拣。

所有包裹都被分拣后，每个包裹分别进入哪个分拣口的方案有多少种？请输出答案对 $10^9+7$ 取模后的结果。

若存在至少一个包裹进入的分拣口不同，则认为两个方案不同。

输入格式

输入的第一行包含两个正整数 $N,M$，分别表示包裹数量和分拣口数量。

输入的第二行包含 $N$ 个正整数 $p_1,p_2,\ldots,p_N$，表示从左到右每个包裹的初始位置。

输入的第三行包含 $M$ 个正整数 $q_1,q_2,\ldots,q_M$，表示从左到右每个分拣口的位置。

输出格式

输出一行一个整数，表示所有包裹进入分拣口的不同方案数对 $10^9+7$ 取模后的结果。

样例1输入

2 2
2 3
1 4

样例1输出

3

样例1解释

从左到右第 $i$ 个包裹称为包裹 $i$，从左到右第 $j$ 个分拣口称为分拣口 $j$。

可能的方案有以下 $3$ 种：

• 包裹 $1$ 进入分拣口 $1$，包裹 $2$ 进入分拣口 $1$；
• 包裹 $1$ 进入分拣口 $1$，包裹 $2$ 进入分拣口 $2$；
• 包裹 $1$ 进入分拣口 $2$，包裹 $2$ 进入分拣口 $2$。

样例2

见选手目录下的 sort/sort2.in 与 sort/sort2.ans。

该样例满足子任务 $1$ 的约束条件。

样例3

见选手目录下的 sort/sort3.in 与 sort/sort3.ans。

该样例满足子任务 $1$ 的约束条件。

样例4

见选手目录下的 sort/sort4.in 与 sort/sort4.ans。

该样例满足子任务 $2$ 的约束条件。

样例5

见选手目录下的 sort/sort5.in 与 sort/sort5.ans。

该样例满足子任务 $3$ 的约束条件。

样例6

见选手目录下的 sort/sort6.in 与 sort/sort6.ans。

该样例满足子任务 $4$ 的约束条件。

样例7

见选手目录下的 sort/sort7.in 与 sort/sort7.ans。

该样例满足子任务 $5$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1 \le N,M \le 10^5$；
• $1 \le p_1 < p_2 < \cdots < p_N \le 10^9$；
• $1 \le q_1 < q_2 < \cdots < q_M \le 10^9$；
• 所有 $p_i$ 与 $q_j$ 两两不同。

若包裹 $i$ 满足 $q_j < p_i < q_{j+1}$，则定义

$$L_i=p_i-q_j,\qquad R_i=q_{j+1}-p_i.$$

对于不在任意两个相邻分拣口之间的包裹，不定义 $L_i,R_i$。

子任务编号	分值	约束条件
$1$	$20$	$1 \le N,M \le 10$
$2$	$5$	$M=1$
$3$	$15$	$M=2$
$4$	$30$	定义了 $L_i,R_i$ 的包裹所对应的不同二元组 $(L_i,R_i)$ 的数量不超过 $1000$
$5$		无额外限制

本题采用捆绑测试。每个子任务内的测试点必须全部通过，才能获得该子任务分数。