吐槽一句：真的是恶评，还有数据范围完全可以开到 (1e5) 的。
做法：推式子
题意
不作赘述。
思路
-
首先分别计算对于所有灯将这条线段所围成的每条线段的点灯方法，因为每条线段上要点的灯的个数一定，但是可以由左端点向右也可以从右端点向左（除了起始和结尾的两条线段），点灯的交错重复构成了一段序列。
则我们要求的便可以简化为：在一段序列上涂色，两种颜色，则涂色方案便是 (2^{len}) 。
但是这是错的，当两边的灯点到只剩一个灯时，点下一个灯对于从左还是从右来说都是一样的，所以方案是 (2^{len-1})。
-
（其实这是个经典问题）因为每段线段点灯的步骤互不干扰。
先考虑两段区间 (A) ， (B) 一共的点亮方案，一种点亮 (A) 区间的方案可以对应一种点亮 (B) 区间的方案，首先的方案数便是 (calc_A imes calc_B) ，其次，合起来的每一种点亮方案可以是 (A) ， (B) 区间交织起来，并且是任意交织，所以合起来每一种方案对应了 (C(len_A+len_B,len_A)) 种方案，相乘便是两个区间一起点亮的方案数，扩展到第三个区间也是如此。
预处理出阶乘和逆元，通过 ( exttt{O(1)}) 算组合数。
时间复杂度 ( exttt{O(NlogN)}) （排序复杂度）。
注意特判开头的区间和结尾的区间，还有两盏灯之间没有灯可以点亮的情况。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000;
const int mod = 1e9+7;
inline int read()
{
int s = 0;
register bool neg = 0;
register char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
neg |= (c == '-');
for (; c >= '0' && c <= '9'; s = s * 10 + (c ^ 48), c = getchar())
;
s = (neg ? -s : s);
return s;
}
int a,b,fac[N+10],inv[N+10],power[N+10],s[N+10];
inline void init() {
fac[0]=fac[1]=inv[0]=inv[1]=power[0]=1;
for(int i=2;i<=N;i++) fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=N;i++) inv[i]=inv[i-1]*inv[i]%mod,power[i]=power[i-1]*2%mod;
}
inline int C(int n,int m) {
return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
signed main()
{
// freopen("in.txt","r",stdin);
init();
a=read();
b=read();
int pre=0,sum=0,ans=1,x=0;
for(int i=1;i<=b;i++) s[i]=read();
sort(s+1,s+b+1);
for(int i=1;i<=b;i++) {
x=s[i];
sum+=x-pre-1;
if(pre!=0&&pre<x-1) ans=(ans*C(sum,x-pre-1)%mod*(power[x-pre-2]))%mod;
pre=x;
}
sum+=a-pre;
ans=(ans*C(sum,a-x))%mod;
printf("%lld",ans);
return 0;
}