1. 这题模数不是常数，所以取模优化很有用
2. 线段树一个节点上可以只维护一个答案矩阵，因为剩下的都是转移矩阵的幂，可以只记录指数
3. lazy tag 是空的就别 push down 了，可以省掉几次矩阵乘法
4. 对每个 $a_i$ 把它离散化后的值提前存下来，不要莫队的时候现查
5. 火车头

我加了这些，最慢点 4.20s（

貌似第二个比较有用