首先 $n \le 15$ 且部分分之间跨度极小，复杂度应该是一些比较奇怪的东西，所以考虑 dp 套 dp（大嘘）

求 LIS 有一个经典的方法就是记录长度为 $i$ 的 IS，最小的结尾，记为 $f_i$，考虑怎么用这个来判断是否存在一个 LIS 是给定的序列：显然，给定序列的任意两项 $a_{pos_i}, a_{pos_{i + 1}}$ 需要满足 $\forall j \in (pos_i, pos_{i + 1}), a_j \gt a_{pos_{i + 1}}$，这就是说扫到 $pos_{i + 1}$ 时，一定会更新 $f_{i + 1}$ 为 $a_{pos_{i + 1}}$，所以合法的转移一定是从 $f_{i + 1} \gt a_{pos_{i + 1}}$ 或 $len \lt i + 1$ 转移过来的（注意还需保证 $a_{pos_i}$ 在 $a_{pos_{i + 1}}$ 之前被填入序列），不难发现只要每次转移保证了这一点就可以保证序列 $a$ 是排列的一个 LIS。

接下来考虑状压 $f$ 数组，由于 $f$ 本身是单调的，一个想法是状压差分数组，但是相邻两项的差分值域可以达到 $n - 1$。另一个比较优秀的想法就是，考虑一个三进制串，第 $i$ 位表示 $i$ 的状态：$0 / 1/ 2$ 分别表示『没有出现过』、『出现过但是当前不在 $f$ 数组中出现』、『出现过且现在在 $f$ 数组中』，那么每次顺序枚举所有数，遇到一个 $2$ 就填一位 $f$ 数组，就能用一次 $O(n)$ 的枚举还原出 $f$ 数组，然后判断是否合法，再转移即可。

本质不同的状态数降低到了 $3^n$，转移的时候需要枚举选哪个数，所以复杂度是 $O(n^2 3^n)$。因为有用的状态很少，所以 应该 可以通过。

注意到你直接开 $3^n$ 长度的滚动数组还是会 MLE，可以写个哈希表，或者只开一个这样长度的数组，每次把有用的状态取出来转移后再放回去就行了。

卡着时限过去了！

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 16, Q = 1145141;
int n, m, tot, a[N], tag[N], f[N], len, pw[N];
bitset<N> vis; pair<int, int> b[Q];
struct hash_table {
	static constexpr int p = 1145141;
	int head[p], cntr;
	struct info { int nxt, key, val; } h[Q];
	inline void mdf(int x, int v) {
		const int pos = x % p;
		for(int i = head[pos]; i; i = h[i].nxt)
			if(h[i].key == x) return h[i].val += v, void();
		h[++cntr] = { head[pos], x, v }, head[pos] = cntr;
	}
	inline void get() {
		for(int i = tot = 0; i < p; ++i)
			for(int j = head[i]; j; j = h[j].nxt)
				b[++tot] = { h[j].key, h[j].val };
		fill(head, head + p, cntr = 0);
	}
} dp;
inline void decode(int S) {
	int x = len = 0; vis.reset();
	for(int i = 1; i <= n; ++i, S /= 3) {
		if((x = S % 3) != 0) vis[i] = 1;
		if(x == 2) f[++len] = i;
	}
}
inline int encode() {
	int S = 0, ptr = 1;
	for(int i = 1; i <= n; ++i)
		S += (vis[i] + (ptr <= len && f[ptr] == i && (++ptr))) * pw[i - 1];
	return S;
}

main() {
	ios :: sync_with_stdio(0), cin.tie(0);
	cin >> n >> m, dp.mdf(0, 1);
	for(int i = pw[0] = 1; i < N; ++i) pw[i] = pw[i - 1] * 3;
	for(int i = 1; i <= m; ++i)
		cin >> a[i], tag[a[i]] = i;
	for(int i = 1; i <= n; ++i) {
		dp.get();  // cerr << "tot = " << tot << '\n';
		for(int j = 1; j <= tot; ++j) {
			const int S = b[j].first, val = b[j].second;
			decode(S); int fir = 0; // get array f & vis
			for(int k = 1; k <= m && !fir; ++k) if(!vis[a[k]]) fir = a[k];
			for(int x = 1; x <= n; ++x) if(!vis[x]) {
				if(tag[x] && x != fir) continue;
				int pos = 0, ini = 0, del = 0;
				if(f[len] < x) {
					if(!tag[x] || len + 1 == tag[x])
						pos = len + 1, ini = 0, f[++len] = x, del = 1;
				} else {
					int t = lower_bound(f + 1, f + len + 1, x) - f;
					if(!tag[x] || t == tag[x]) pos = t, ini = f[t], f[t] = x;
				}
				if(!pos) continue; // 不合法的转移
				vis[x] = 1, dp.mdf(encode(), val);
				f[pos] = ini, len -= del, vis[x] = 0;
			}
		}
	}
	dp.get(); int res = 0;
	for(int j = 1; j <= tot; ++j) {
		int S = b[j].first, val = b[j].second;
		decode(S); if(len == m) res += val; // final check
	}
	cout << res << '\n';
}