定义序列 $A_1,A_2,\cdots,A_n$ 的异或差分 $B_i=A_i\operatorname{xor}A_{i+1}$。可以发现如果检测失败，一定存在 $[x,x+1],[y,y+1]$ 使其检测失败。如果所有 $x,y\in[1,n)\land x\neq y$ 都检测成功，就合法。

考虑 $H_x,H_y$，如果 $H_x=H_y=\tt 0$，那么如果 $B_x=B_y$ 就检测失败，否则成功；如果 $H_x=\tt 1$ 或 $H_y=\tt 1$，那么其中一个数修改为 $2^k$ 就可以使得 $B_x\neq B_y$。

将 $H_i=\tt 1$ 看做在异或差分里覆盖相邻的两个数 $i-1,i$，合法条件就是没有被覆盖的数不能相同。特别地，$H_1=\tt 1$ 只会覆盖 $1$，而 $H_n=\tt 1$ 只会覆盖 $n-1$。

由于 $V=2^k$，所以每个异或差分出现的概率相等，可以不用管原序列具体是啥。假设剩下 $x$ 个没覆盖的位置，就有 $\dfrac{V!}{(V-x)!}\times V^{n-1-x}$ 种填数的方案，我们考虑数覆盖方案。

接下来做法很多，介绍一种做法。

在一个位置修改会影响它和后面的数。设 $f_{i,j}$ 是前 $i$ 个位置被覆盖、$i+1$ 未被覆盖，$[1,i]$ 中有 $j$ 个位置未被覆盖，且 $i-1$ 被修改的方案数。$g_{i,j}$ 是前 $i$ 个位置被覆盖、$i+1$ 未被覆盖，$[1,i]$ 中有 $j$ 个位置未被覆盖，且 $i-1$ 没有被修改的方案数。

由于 $i+1$ 未被覆盖，$i$ 处肯定没有修改。我们考虑加入对 $i-1$ 的修改来转移 $f_{i,j}$：

• $i-1$ 已被覆盖：需要满足 $i-1$ 没有修改过，方案数是 $f_{i-1,j}$。
• $i-1$ 未被覆盖：前面 $i-2$ 个随便填，$f_{i-2,j}+g_{i-2,j}$。

我们考虑空出 $i$ 来转移 $g$：

• 前面 $i-1$ 个随便填，$f_{i-1,j-1}+g_{i-1,j-1}$。

综上：

$$\begin{cases} f_{i,j}=f_{i-1,j}+f_{i-2,j}+g_{i-2,j}\\ g_{i,j}=f_{i-1,j-1}+g_{i-1,j-1} \end{cases} $$

答案就是 $\displaystyle\frac{1}{V^{n-1}}\sum_{i=0}^{n-1}(f_{n,i}\times 2+g_{n,i})\times\frac{V!}{(V-i)!}\times V^{n-1-i}$ 。

直接做是 $\mathcal{O}(n^2)$，期望得分 $60$，我们考虑优化。

令 $F_i(x)=\sum_{j=0}^{\infty}f_{i,j}x^i$，$G_i(x)=\sum_{j=0}^{\infty}g_{i,j}x^i$

转移可以写成：

$$\begin{cases} F_i(x)=F_{i-1}(x)+F_{i-2}(x)+G_{i-2}(x)\\ G_i(x)=xF_{i-1}(x)+xG_{i-1}(x) \end{cases} $$

可以写成 $2\times 2$ 矩阵：

$$\begin{bmatrix} 1,1\\ 1,x\\ \end{bmatrix} \begin{bmatrix}F_{i-1}(x)\\F_{i-2}(x)+G_{i-2}(x)\end{bmatrix} = \begin{bmatrix}F_{i}(x)\\F_{i-1}(x)+G_{i-1}(x)\end{bmatrix} $$

直接对着这个分治 NTT 就可以两个 log，视常数可以获得 $60\sim80$ 分。

不过观察到答案次数只有 $n-1$，我们直接把每个单位根带进去，矩阵快速幂 $\mathcal{O}(2^3\times\log n)$ 算出答案，然后一遍 DNTT 插出来原多项式就可以了。

时间复杂度 $\mathcal{O}(n\log n)$，期望得分 $100$。常数似乎不是太大，std 极限数据不到 0.25s。

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
using namespace std;
namespace Math {
	typedef long long LL;
	template <class T> T qpow(T a, LL b) { if (!b) return {1}; T rs = a; b --; for (; b; b >>= 1, a = a * a) if (b & 1) rs = rs * a; return rs; }
	LL mul(LL a, LL b, LL p) { LL rs = a * b - LL(1.L * a * b / p) * p; rs %= p; if (rs < 0) rs += p; return rs; }
	template <unsigned P = 0> struct mint {
		unsigned v; static unsigned mod; mint() = default;
		template <class T> mint(T x) { x %= getmod(), v = x < 0 ? x + getmod() : x; }
		static int getmod() { if (P > 0) return P; else return mod; }
		static void setmod(unsigned m) { mod = m; }
		mint operator + () const { return *this; }
		mint operator - () const { return mint(0) - *this; }
		mint inv() const { return assert(v), qpow(*this, getmod() - 2); }
		int val() const { return v; }
		mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }
		mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }
		mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }
		mint &operator /= (const mint &q) { return *this *= q.inv(); }
		friend mint operator + (mint p, const mint &q) { return p += q; }
		friend mint operator - (mint p, const mint &q) { return p -= q; }
		friend mint operator * (mint p, const mint &q) { return p *= q; }
		friend mint operator / (mint p, const mint &q) { return p /= q; }
		friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }
		friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }
		friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }
		friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }
		friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }
		friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }
		friend istream &operator >> (istream &is, mint &a) { is >> a.v; return is; }
		friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }
	};
	template <> unsigned mint<0>::mod = 998244353;
}
namespace PolyNTT {
	const int maxn = 2e6 + 5, mod = 998244353, _G = 3;
	typedef Math::mint<mod> MI;
	int st; MI inv, w[maxn], wi[maxn];
	void init(int n) {
		st = 1 << (__lg(n) + 1), inv = mod - (mod - 1) / st;
		w[0] = wi[0] = 1;
		for (int i = 1; i < st; i <<= 1)
			w[i] = Math::qpow((MI)_G, ((mod - 1) >> 2) / i), wi[i] = Math::qpow((MI)_G, mod - 1 - ((mod - 1) >> 2) / i);
		REP(i, 1, st - 1) w[i] = w[i & (i - 1)] * w[i & -i], wi[i] = wi[i & (i - 1)] * wi[i & -i];
	}
	void NTT(MI* a, int n = st) {
    	for (int l = n >> 1, r = n; l; l >>= 1, r >>= 1)
	        for (int j = 0, o = 0; j != n; j += r, ++ o)
	            for (int k = j; k != j + l; ++ k) {
	            	MI x = a[k], y = a[k + l] * w[o];
					a[k] = x + y, a[k + l] = x - y;
				}
	}
	void DNTT(MI* a, int n = st) {
	    for (int l = 1, r = 2; l < n; l <<= 1, r <<= 1)
	        for (int j = 0, o = 0; j != n; j += r, ++ o)
	            for (int k = j; k != j + l; ++ k) {
	            	MI x = a[k], y = -a[k + l];
	            	a[k] = x - y, a[k + l] = (x + y) * wi[o];
				}
	}
}
namespace Milkcat {
	using namespace Math;
	using namespace PolyNTT;
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 2e6 + 5, mod = 998244353;
	typedef Math::mint<mod> MI;
	struct mat {
		MI A, B, C, D;
		mat(MI _0, MI _1, MI _2, MI _3) : A(_0), B(_1), C(_2), D(_3) {}
		friend mat operator * (const mat& x, const mat& y) {
			return mat(
				x.A * y.A + x.B * y.C,
				x.A * y.B + x.B * y.D,
				x.C * y.A + x.D * y.C,
				x.C * y.B + x.D * y.D
			);
		}
	};
	int n, k; MI m, rs, pw[N], C[N], F[N];
	int main() {
		cin >> n >> k, m = qpow((MI)2, k);
		
		init(n), F[1] = 1, NTT(F);
		REP(i, 0, st - 1) {
			mat b(1, 1, 1, F[i]), rs(1, 0, 0, 0);
			for (int t = n; t; t >>= 1, b = b * b)
				if (t & 1) rs = b * rs;
			F[i] = rs.A + rs.C;
		} 
		DNTT(F);
		REP(i, 0, st - 1) F[i] *= inv;
	
		pw[0] = C[0] = 1;
		REP(i, 1, n) pw[i] = pw[i - 1] * m, C[i] = C[i - 1] * (m - i + 1);
		REP(i, 0, n - 1) rs += F[i] * pw[n - 1 - i] * C[i];
		cout << rs / qpow(m, n - 1) << '\n';
		
		return 0;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}