把所有状态表示为一个整数 $i$，其中 $i$ 在 $[0,6^n)$ 之间，$i$ 在 $6$ 进制下第 $k$ 位表示第 $k$ 个排列的编号。

首先概率不好直接求，考虑转成期望。显然，以 $i$ 结束的概率就是经过状态 $i$ 的期望次数乘上当前在状态 $i$ 下一步直接结束的概率。

后者显然是 $\frac 1m$，于是只需求出经过每个状态的期望次数。

设 $g_i$ 表示选到状态为 $i$ 的突变枪的概率，设 $f_i$ 为经过状态 $i$ 的期望次数，则有：

$$f_i=[i=0]+\sum\limits_{j\circ k=i}f_jg_k$$

直接解方程可以得到 $216^n$ 的做法。

这个卷积关于 $6$ 进制下每一位是独立的，这让我们可以从类似 FWT 的角度考虑这个问题。

考虑 A 性质如何解决，可以发现 A 性质的排列复合等价于给编号做 $3$ 进制不进位加法。这就是一个经典的 $3$ 进制 FWT。

不妨设 $(f\circ g)_i=\sum\limits_{j\circ k=i}f_jg_k$，设 $h_i=[i=0]$，则：

$$f_i=h_i+(f\circ g)_i$$

$$f=h+f\circ g$$

在 $\circ$ 是 $3$ 进制不进位加法的情况下，我们知道存在一种变换 $FWT(f)$，满足 $FWT(f\circ g)=FWT(f)\cdot FWT(g)$，其中 $\cdot$ 表示两个数组对位相乘得到的结果。

两边同时 FWT 得到：

$$FWT(f)=FWT(h+f\circ g)$$

$$=FWT(h)+FWT(f\circ g)$$

$$=FWT(h)+FWT(f)\cdot FWT(g)$$

即：

$$FWT(f)_i=FWT(h)_i+FWT(f)_i\times FWT(g)_i$$

由于 $g,h$ 已知，所以可以直接先求出 $FWT(g)$ 和 $FWT(h)$，然后解出来每个 $FWT(f)_i$，最后 $IFWT$ 即可得到 $f$。

现在考虑 $\circ$ 是排列复合时的情况。

但是我们没有针对排列复合的现成的 FWT 可以用，于是考虑手造。

首先考虑最一般的 FWT 是如何推导的。

FWT 是线性变换，本质上就是矩阵乘法。也就是我们需要构造一个矩阵 $w$，使得 $FWT(f)_i=\sum\limits_{j}f_j w_{i,j}$。$FWT(f)$ 实际上就是 $f$ 左乘上矩阵 $w$ 得到的结果。

还要求满足 $FWT(f\circ g)_i=FWT(f)_i\cdot FWT(g)_i$。

展开得：

$$\sum\limits_j(f\circ g)_j w_{i,j}=\sum\limits_{j}f_jw_{i,j}\sum\limits_{k}g_kw_{i,k}$$

再把 $f\circ g$ 展开得：

$$\sum\limits_{j}\sum\limits_{a\circ b=j}f_ag_bw_{i,j}=\sum\limits_{j}f_jw_{i,j}\sum\limits_{k}g_kw_{i,k}$$

也就是：

$$\sum\limits_{a}\sum\limits_{b}f_ag_bw_{i,a\circ b}=\sum\limits_{j}\sum\limits_{k}f_jg_kw_{i,j}w_{i,k}$$

可以发现，只需要我们的 $w$ 满足 $w_{i,a\circ b}=w_{i,a}w_{i,b}$ 即可。

FWT 比朴素暴力快的地方就在于如果 $w$ 是关于每一位独立的，也就是 $w_{i,j}$ 可以表示为 $k$ 进制下每一位的贡献相乘，那么对于有这样性质的矩阵，我们可以在较低的复杂度内做矩阵乘法。

设 $i_t$ 表示 $i$ 在题目需要的进制下（本题为 6 进制）的第 $t$ 位，如果 $w$ 还满足 $w_{i,j}=\prod\limits_{t}w_{i_t,j_t}$，则可以在较低的复杂度内给一个向量左乘上 $w$，也就可以解决这道题。

考虑如何找到这样的 $w$。如果 $w$ 满足 $w_{i,j}=\prod\limits_t w_{i_t,j_t}$，则

$$\prod\limits_t w_{i_t,(a\circ b)_t}=\prod\limits_t w_{i_t,a_t}\prod\limits_t w_{i_t,b_t}$$

可以发现只需满足找到一个 $6\times 6$ 的矩阵满足 $w_{i,a\circ b}=w_{i,a}w_{i,b}$ 即可。

由于需要 $IFWT$，所以我们的矩阵需要有逆。

可以发现上面的式子对于矩阵每一行独立，也就是只需找到 $6$ 组线性无关的 $w$，满足 $w_aw_b=w_{a\circ b}$。

实际上，我们在 $3$ 个数组上的变换不需要相同，我们也可以设计 $3$ 种不同的变换，同样可以用上面的方法求出答案。

也就是我们只需找到 $6$ 组 $w_1,w_2,w_3$，使得 $w_3$ 线性无关且满足 $w_{1,a}w_{2,b}=w_{3,a\circ b}$。

于是可以写个爆搜，搜出来合法的 $w$。

很不幸，我们只能搜出来两组本质不同的 $w_3$。分别是：$\{1,1,1,1,1,1\}$ 和 $\{1,-1,-1,1,1,-1\}$。

于是我们考虑接着扩展我们的做法。

一个想法是增加信息的复杂程度。注意到我们只需满足 $w_{a}w_b=a_{a\circ b}$，满足 $w$ 可逆，但是 $w$ 不一定要是整数。

于是一种想法是把 $w$ 变成 $2\times 2$ 的矩阵。写个爆搜可以发现我们可以找到很多矩阵组 $w$，满足上述的式子，并且在其中可以轻松找到很多线性无关的 $6$ 元组。

但是这么写有一个大问题：矩阵没有交换律。

我们上面推导的时候，有一步是要求 $\prod\limits_t w_{a_t}w_{b_t}=\prod\limits_t w_{a_t}\prod\limits_t w_{b_t}$ 成立，但是这个式子在 $w$ 是矩阵的情况下是不成立的。

于是我们接着扩展做法。一个想法是我们找到一种运算，把 $w$ 定义为 $6$ 进制下每一位的贡献用这种运算复合起来，并且这种运算能支持上面的式子成立。

也就是想办法找到一个运算 $\oplus$，使得 $\bigoplus\limits_{t}\left(w_{a_t}\times w_{b_t}\right)=\left(\bigoplus\limits_tw_{a_t}\right)\times\left(\bigoplus\limits_tw_{b_t}\right)$，其中 $\times$ 是矩阵乘法。

于是我们考虑这么一种运算：

$n\times m$ 的矩阵 $A$ 和 $a\times b$ 的矩阵 $B$，$A\oplus B$ 的结果是一个 $n\times a$ 行 $m\times b$ 列的矩阵 $C$，满足 $C_{i,j}=A_{\lfloor\frac ia\rfloor,\lfloor\frac jb\rfloor}B_{i\mod a,j\mod b}$。也就是扩展 Kronecker 乘法。

可以发现，这种运算满足了我们需要的所有性质。

于是我们得到了一个做法：先做 $FWT$，其中把乘法改成扩展 Kronecker 乘法。

然后对变换后的结果解方程，再做逆变换。

由于 $w$ 都是 $2\times 2$ 的矩阵，所以最终得到的矩阵都是 $2^n\times 2^n$ 的，复杂度就是 $48^n$。

考虑接着优化，接着扩展我们的做法。

实际上，我们的矩阵也不一定要是 $6\times 6$ 的。我们完全可以换成一个更小的矩阵，只要保证我们能够求逆回去即可。

而由于我们的 $w$ 里面是矩阵，所以一个更小的矩阵也可以有足够的信息让我们逆变换回去。

此外，$w$ 里面也不一定非要全是矩阵，我们完全可以让 $w$ 里面随便填，只要定义出来所有的“乘法”，就能做 FWT。

于是我们考虑让 $w$ 是一个 $3\times 6$ 的矩阵，其中前两行是标量，分别是上文搜出来的 $\{1,1,1,1,1,1\}$ 和 $\{1,-1,-1,1,1,-1\}$，第 $3$ 行是矩阵。

标量和矩阵的乘法就直接给矩阵内每个位置乘上这个标量。可以发现这种定义依然满足条件。

此时，FWT 出来的数组和原数组就不等长了。在 $w$ 是 $3\times 6$ 的矩阵是，FWT 出来的结果是 $3^n$ 的数组，其中每个元素是大小不一的矩阵。

由于每一行要么全是标量要么全是矩阵，所以每个位置得到的矩阵大小都只跟这个位置的下标有关，所有加法是可以定义的。

按照这种方法，我们会得到 $\binom{n}{i}2^{n-i}$ 个 $2^i\times 2^i$ 的矩阵。对每个矩阵分别求逆，总复杂度是 $O(10^n)$，FWT 复杂度为 $O(6^nn)$。

接下来是实现上的细节。

由于矩阵总大小恰好是 $6^n$，可以直接把转移矩阵的第三行展开成 $4$ 行，得到 $6\times 6$ 的标量矩阵，然后直接用这个矩阵 FWT。最后再找出来每个矩阵的每个元素在数组的哪个位置。