【题目描述】：
    给出1~n的一个排列的一个最长上升子序列，求原排列可能的种类数。
【题目解法】：
    一开始交评测姬卖萌，300+ms就给我返回了TLE TAT
    之前做过一道类似的DP套DP的题目，那题我是用f[i]表示以i结尾的LIS长度，然后利用前缀max来获得状态
    这题我们如法炮制，利用前缀和作为状态
    但是由于这题为一个排列，因此我们必须修改状态
    我们用一个3进制表示状态：2表示该位置没有填，0 1分别表示意味着比上一个不为2的位置的LIS前缀和大0 1
    每一次转移我们必定是将一个2变成0或1，因此状态一定变小，我们倒着DP即可
    每次转移，如果枚举的这个数字在给定的LIS中，我们先判断他的前面一个是否加进去，并且判断加入之后以他为结尾的LCS是否为给定的长度，并且最长的LIS是否大于给定的LIS长度，暴力转移即可
    复杂度O(N^2*3^N)
    然后这只是理论复杂度，实际上远远达不到这个上界

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=20;
const int M=14348907;
int n,m,S,a[N],f[M],state[N],g[N];
bool v[N]; int fac[N],len[N],ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint(); m=getint(); fac[0]=1;
    for (int i=1; i<=n; i++) fac[i]=fac[i-1]*3; S=fac[n]-1;
    for (int i=1; i<=m; i++) a[i]=getint(),v[a[i]]=true,len[a[i]]=i;
}
inline bool GetState(int nowS)
{
    int pre=0; bool flag=false;
    for (int i=1; i<=n; i++,nowS/=3)
    {
        int now=nowS%3;
        if (now==2) flag=true,state[i]=-1,g[i]=pre;
        if (now==1) state[i]=++pre;
        if (now==0) state[i]=pre;
    }
    return flag;
}
inline int ZipState()
{
    int pre=0,nowans=0;
    for (int i=1; i<=n; i++)
    {
        if (state[i]==-1) {nowans+=2*fac[i-1]; continue;}
        int now=max(pre,state[i]); nowans+=(now-pre)*fac[i-1]; pre=now;
    }
    return nowans;
}
void solve()
{
    f[S]=1; ans=0;
    for (int i=S; i>=1; i--)
    {
        if (f[i]==0) continue;
        if (!GetState(i)) {ans+=f[i]; continue;}
        for (int j=1; j<=n; j++)
        {
            if (state[j]!=-1) continue;
            if (!v[j])
            {
                if (g[j]+1>m) continue;
                state[j]=g[j]+1; f[ZipState()]+=f[i]; state[j]=-1; continue;
            }
            int pre=a[len[j]-1];
            if ((len[j]!=1)&&(state[pre]==-1)) continue;
            if (g[j]+1!=len[j]) continue;
            state[j]=g[j]+1; f[ZipState()]+=f[i]; state[j]=-1; continue;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}