$\text {\color{Red} 本题很卡常！！！ }$

以下是卡常方案，希望对大家有所帮助！

矩阵开 4*4 就OK了，下标从零开始算

不要偷懒一直用重载好的矩阵乘法运算符，那个答案向量和转移矩阵的乘积单独写一个 $n^2$ 的计算函数，可以降很多常数。

矩阵中的数据开 int 就够了，乘法的时候前面 1ll* 就OK 了（小心爆 int）（开了 long long 见祖宗）

实测 ：

ios::sync_with_stdio(false);
cin.tie(nullptr);

在 O2 加持下跑得比一般的 printf 和快读还要快！