今天 rand 到了这道题，发现之前做过就直接交上去，然后被卡常了。

不过当时我的做法是矩阵快速幂+神秘分块，被卡卡也算正常。

首先是取模优化，尤其是懒取模，都给加上。

最关键的是矩阵乘法部分的取模，一定要先算完了之后再取模，会快很多。