[Luogu4007] 小 Y 和恐怖的奴隶主

期望 DP，只维护合法的状态。

每次询问暴力做矩阵快速幂会超时，所幸，对于所有询问，要做快速幂的矩阵是相同的，并且我们只需要向量乘矩阵幂后的结果。所以可以预处理出快速幂所需要的中间量，即 $A^{2^k}$ 处的取值，快速幂就只需 $\log n$ 次向量乘矩阵，时间开销由 $O(Tm^3\log n)$ 优化为 $O(m^3\log n+Tm^2\log n)$。