配点 : $900$ 点

問題文

数直線上に $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$ 通りの組合せが異なるとは、あるロボットが存在し、そのロボットの通った出口が異なることを言います。

制約

• $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$ で割った余りを出力せよ。

2 2
2 3
1 4

3

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

• $($出口 $1$$,$ 出口 $1$$)$
• $($出口 $1$$,$ 出口 $2$$)$
• $($出口 $2$$,$ 出口 $2$$)$

3 4
2 5 10
1 3 7 13

8

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

4 1
1 2 4 5
3

1

どのロボットも出口 $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