我们考虑转化题意，一个合法的将 \(1\sim N\) 划分成长度依次为 \(a_1,a_2,\cdots a_k\) 的小区间，对答案的贡献为 \(a_1^2a_2^2\cdots a_k^2\)。
化贡献为方案数，我们在每个长度为 \(a_i\) 的小区间内放置两个独立的标记，每个合法的划分方案对放置标记方案种数的贡献恰好是其对最终答案的贡献权值。并且每个划分方案的标记方案互不重合。
然后我们就可以 \(dp\)，设 \(dp_{i,mask}\) 表示目前处理到第 \(i\) 个小格子，目前区间已经安放标记的状态为 \(mask\) 的方案数量。其中 \(mask\) 是一个长度为 \(2\) 的二进制串，表示第一个和第二个标记分别有没有被放下。
然后考虑从 \(dp_i\) 到 \(dp_{i+1}\) 的转移，其实就是讨论：
-
在 \(i\) 和 \(i+1\) 之间是否放置划分点
-
在 \(i+1\) 这个位置怎么放标记
首先是不放置划分点，那么每个 \(mask\) 就只能转移到 \(new\wedge mask=mask\) 的状态，也就是 \(\{0\rightarrow 0,1,2,3\}\{1\rightarrow 1,3\}\{2\rightarrow 2,3\}\{3\rightarrow 3\}\)。
然后是放置划分点，首先上一个要已经放完标记，所以只能从 \(3\) 转移过去，而下面变成 \(0\)，\(i+1\) 随便放，也就是 \(\{3\rightarrow 0,1,2,3\}\)。
我们发现，这样就可以矩阵快速幂了，在 \(i\in X\) 的时候，转移就是矩阵
\[D_1=\begin{pmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{pmatrix}\]在 \(i\notin X\) 的时候，就加上放置划分点的转移变成
\[D_2=\begin{pmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 2 \end{pmatrix}\]注意两种 \(3\) 到 \(3\) 的转移是分开的，所以权值是 \(2\)。
然后用 \(X\) 中的数分段，段内部 \(D_2\) 矩阵快速幂，段和段之间用 \(D_1\) 乘上即可。
复杂度 \(O(4^3m\log n)\)（事实上可以做到 \(3\times 3\) 的矩阵，但是转移不如 \(4\times 4\) 来得直观）（但是跑得实在是很慢啊）
const int P=1000000007;
struct matrix{
vt<vt<int> >a;
matrix(){};
matrix(int n,int m){
vt<vt<int> >vv(n,vt<int>(m,0));
a=vv;
}
matrix operator *(const matrix b)const{
matrix res;
vt<vt<int> >vv(a.size(),vt<int>(b.a[0].size(),0));
rd(i,(int)a.size())rd(j,(int)b.a[0].size())rd(k,(int)b.a.size()){
vv[i][j]=(vv[i][j]+1ll*a[i][k]*b.a[k][j]%P)%P;
}
res.a=vv;
return res;
}
};
matrix fpow(matrix a,ll k){
if(k==1)return a;
matrix res=fpow(a,k>>1);
if(k&1)return res*res*a;
return res*res;
}
int n,m,x[100005];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
rp(i,m)cin>>x[i];x[m+1]=n;x[0]=-1;
matrix dp(1,4);
dp.a[0][0]=1;
matrix tf(4,4),ty(4,4);
rd(i,4)rd(j,4)if((i&j)==i)tf.a[i][j]=1;
ty=tf;
rd(i,4)ty.a[3][i]=1;
ty.a[3][3]=2;
matrix bb=fpow(ty,2);
rep(i,1,m+1){
int len=x[i]-x[i-1]-1;
if(len>0)dp=dp*fpow(ty,len);
if(i!=m+1)dp=dp*tf;
}cout<<dp.a[0][3]<<endl;
return 0;
}
//Crayan_r