题目描述

数直線上に $N$ 体のロボットと $M$ 個の出口があります。 これらの $N\ +\ M$ 個の座標はすべて整数であり、すべて相異なります。 各 $i$ ($1\ \leq\ i\ \leq\ N$) について、左から $i$ 番目のロボットの座標は $x_i$ です。 また、各 $j$ ($1\ \leq\ j\ \leq\ M$) について、左から $j$ 番目の出口の座標は $y_j$ です。

すぬけ君は、次の $2$ 種類の操作を好きな順序で繰り返し行い、ロボットを一斉に動かすことができます。

• 数直線上のすべてのロボットの座標を $-1$ する。
• 数直線上のすべてのロボットの座標を $+1$ する。

各ロボットは、いずれかの出口と重なった瞬間、その出口を通って数直線上から消えます。 すぬけ君は、すべてのロボットが消えるまで操作を行い続けます。

すべてのロボットが消えた後、各ロボットがどの出口を通ったかという組合せは何通りありうるでしょうか？ $10^9\ +\ 7$ で割った余りを求めてください。 ただし、$2$ 通りの組合せが異なるとは、あるロボットが存在し、そのロボットの通った出口が異なることを言います。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $x_1$ $x_2$ $...$ $x_N$ $y_1$ $y_2$ $...$ $y_M$

输出格式

すべてのロボットが消えた後、各ロボットがどの出口を通ったかという組合せは何通りありうるか？ $10^9\ +\ 7$ で割った余りを出力せよ。

题目大意

现在有 $n$ 个机器人和 $m$ 个出口在一个数轴上，每个机器人和出口都有一个正整数坐标，并且这 $n+m$ 个坐标都互不相同

现在执行若干次操作，每次操作可以是：

• 将所有机器人的坐标减一
• 将所有机器人的坐标加一

当一个机器人移到出口的的时候他就会消失

操作将进行直到所有机器人消失

两种操作序列不同，当且仅当存在至少一个机器人在两次操作序列进行完成后从不同的出口消失

给出每个机器人和出口的坐标，求有多少种不同的操作序列，输出方案数对 $10^9+7$ 取模的结果

坐标 $\leq10^9$

$1\leq n,m\leq 10^5$

2 2
2 3
1 4

3

3 4
2 5 10
1 3 7 13

8

4 1
1 2 4 5
3

1

4 5
2 5 7 11
1 3 6 9 13

6

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\ <\ ...\ <\ x_N\ \leq\ 10^9$
• $1\ \leq\ y_1\ <\ y_2\ <\ ...\ <\ y_M\ \leq\ 10^9$
• 与えられる座標はすべて整数である。
• 与えられる座標はすべて相異なる。

Sample Explanation 1

左から $i$ 番目のロボットをロボット $i$ と呼び、左から $j$ 番目の出口を出口 $j$ と呼びます。 $($ロボット $1$ が通った出口$,$ ロボット $2$ が通った出口$)$ の組合せとしてありうるものは、次の $3$ 通りです。 - $($出口 $1$$,$ 出口 $1$$)$ - $($出口 $1$$,$ 出口 $2$$)$ - $($出口 $2$$,$ 出口 $2$$)$

Sample Explanation 2

各ロボットごと独立に通る出口を決められるので、組合せは $2^3\ =\ 8$ 通りです。

Sample Explanation 3

どのロボットも出口 $1$ を通ります。