ARC101F
有(n)个机器人，有(m)个洞，分布在一个数轴上。
每次可以将所有机器人往左或往右移动一格。
问不同的机器人掉入洞的方案数（两个方案不同，当且仅当存在一个机器人掉入了不同的洞）。
(nle 10^5)
吼题。
首先记每个机器人向左和向右移动多少步就可以掉进坑中。（左边或右边没有坑的机器人忽略）
用个二元组((l,r))来记：向左最多移动了(l)，向右最多移动了(r)。
操作相当于((l,r))变成((l+1,r))或((l,r+1))。
把它画在平面直角坐标系上，机器人变成点。于是我们要求的是：画一条折线，折线分割平面形成两个集合不同的方案数。
为了不重不漏，将这条折线往下压。于是折线的转角处（横变成竖）的位置是个机器人所对应的点。
直接DP：(f_i=1+sum_{x_j<x_i,y_j<y_i}f_j)
最后统计答案可以钦定一个((+infty,+infty))的点，统计到它的答案。（其实这也相当于(sum f_i+1)）
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define INF 1000000817
#define mo 1000000007
#define ll long long
int n,m;
int a[N],b[N];
int nq;
pair<int,int> q[N];
int p[N],np;
int f[N];
int t[N];
void add(int x,int c){
for (;x<=np;x+=x&-x)
(t[x]+=c)%=mo;
}
int query(int x){
ll r=0;
for (;x;x-=x&-x)
r+=t[x];
return r%mo;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
scanf("%d",&b[i]);
for (int i=1;i<=m;++i)
scanf("%d",&a[i]);
for (int i=1,j=1;i<=n;++i){
for (;j<=m && a[j]<b[i];++j);
if (j==m+1 || j==1) continue;
q[++nq]=make_pair(a[j]-b[i],b[i]-a[j-1]);
}
for (int i=1;i<=nq;++i)
p[++np]=q[i].second;
sort(p+1,p+np+1);
np=unique(p+1,p+np+1)-p-1;
for (int i=1;i<=nq;++i)
q[i].second=-(lower_bound(p+1,p+np+1,q[i].second)-p);
sort(q+1,q+nq+1),nq=unique(q+1,q+nq+1)-q-1;
// for (int i=1;i<=nq;++i)
// printf("%d %d
",q[i].first,q[i].second);
for (int i=1;i<=nq;++i){
f[i]=1+query((-q[i].second)-1);
add(-q[i].second,f[i]);
}
ll ans=1;
for (int i=1;i<=nq;++i)
ans+=f[i];
ans%=mo;
printf("%lld
",ans);
return 0;
}