我们有 Cayley-Hamilton 定理以说明答案至多是 $K$ 阶线性递推，其中 $K=166$ 是矩阵边长。事实上，通过 Berlekamp-Massey 算法可以得到的最短递推式长度为 $K=147$。

于是我们立刻得到 $O(TK^2\log n)$ 或 $O(TK\log K\log n)$ 做法，但前者需要卡常，后者需要 FFT。

事实上我们可以稍微平衡一下复杂度。令特征多项式为 $Q(x)$，我们无非是要求出 $x^n \bmod Q(x)$。不妨模仿光速幂，设步长 $B$，预处理 $x^{B^k, 2 B^k, \dots, (B-1)B^k} \bmod Q(x)$，预处理时间复杂度为 $O(B K^2 \log_B n)$ 或 $O(B K \log K \log_B n)$。
而询问复杂度为 $O(T K^2 \log_B n)$ 或 $O(T K \log K \log_B n)$。

取 $B = \Theta(T)$ 可得 $O(T K^2 \log_T n)$ 或 $O(T K\log K\log_T n)$。但我的代码似乎取 $B = 2^6$ 比较快。