因为是一个排列，所以可以用$n$位二进制数来表示$O(nlog n)$求LIS时的单调栈。
首先通过$O(n^22^n)$的预处理，求出每种LIS状态后面新加一个数之后的状态。
设$f[i][j]$表示已选数字集合为$i$，LIS状态为$j$的方案数。
转移时枚举不在$i$里的数$t$，如果$t$在给定的LIS中，那么它加入时需要检验它的前一个是否已经被加入。
对于状态的存储，可以考虑三进制，0表示没选，1表示选了但是不在栈中，2表示在栈里。那么只要将两个二进制数看作三进制，然后相加即可。
时间复杂度$O(n3^n)$。
#include<cstdio>
#define N 15
int n,m,i,j,k,p[N],g[N][1<<N],pow[N],a[1<<N],f[14348907],ans;
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)p[i]=-1;
for(i=0;i<m;i++)scanf("%d",&j),p[j-1]=k-1,k=j;
for(pow[0]=i=1;i<n;i++)pow[i]=pow[i-1]*3;
for(i=0;i<1<<n;i++)for(j=0;j<n;j++)if(!(i>>j&1)){
g[j][i]=i|(1<<j);
for(k=j+1;k<n;k++)if(i>>k&1)break;
if(k<n)g[j][i]^=1<<k;
}else a[i]+=pow[j];
for(i=0;i<n;i++)if(p[i]<0)f[pow[i]<<1]=1;
for(i=1;i<1<<n;i++)for(k=0;k<n;k++)if(!(i>>k&1)){
if(~p[k])if(!(i>>p[k]&1))continue;
for(j=i;j;j=(j-1)&i)if(f[a[i]+a[j]])f[a[i|(1<<k)]+a[g[k][j]]]+=f[a[i]+a[j]];
}
for(i=1;i<1<<n;i++)if(__builtin_popcount(i)==m)ans+=f[a[(1<<n)-1]+a[i]];
return printf("%d",ans),0;
}