常数与空间都不大，并且不需要使用其他卡常方式！记录

注意到我们维护的线段树区间矩阵和只有第一行有用，所以可以只开一维数组（懒标记正常 4*4）

struct SMT {
	int qjm[4];
}Tree[maxn << 2], a[maxn];

struct _SMT {
	bool fl;
	int qjm[4][4];
}Lazy[maxn << 2];

//矩阵加
inline void P(SMT &ans, SMT a, SMT b) { F(i, 0, 3) ans.qjm[i] = ((ll)a.qjm[i] + b.qjm[i]) % mod; }
//矩阵乘
inline void M(SMT &ans, SMT a, _SMT b) { F(i, 0, 3) { ans.qjm[i] = 0; F(j, 0, 3) (ans.qjm[i] += ((ll)a.qjm[j] * b.qjm[j][i]) % mod) %= mod; } }
inline void M(_SMT &ans, _SMT a, _SMT b) { F(i, 0, 3) F(j, 0, 3) { ans.qjm[i][j] = 0; F(k, 0, 3) (ans.qjm[i][j] += ((ll)a.qjm[i][k] * b.qjm[k][j]) % mod) %= mod; } }
//矩阵 =
inline void Z(SMT &ans, SMT a) { F(i, 0, 3) ans.qjm[i] = a.qjm[i]; }
inline void Z(_SMT &ans, _SMT a) { F(i, 0, 3) F(j, 0, 3) ans.qjm[i][j] = a.qjm[i][j]; }

同时我们并不需要每次都 PushDown 一次，打标记即可（即 _SMT 中的 fl）

inline void PushDown(int p) {
	if(Lazy[p].fl) {
		M(Tree[p << 1], Tree[p << 1], Lazy[p]);
		M(Tree[p << 1 | 1], Tree[p << 1 | 1], Lazy[p]);
		M(Lazy[p << 1], Lazy[p << 1], Lazy[p]);
		M(Lazy[p << 1 | 1], Lazy[p << 1 | 1], Lazy[p]);
		Z(Lazy[p], I);
		Lazy[p].fl = 0;
		Lazy[p << 1].fl = Lazy[p << 1 | 1].fl = 1; 
	}
}

inline void Modify(int p, int l, int r, int s, int t, _SMT q) {
	if(s <= l && r <= t) return M(Tree[p], Tree[p], q), M(Lazy[p], Lazy[p], q), Lazy[p].fl = 1, void();
	int mid = (l + r) >> 1;
	PushDown(p);
	if(s <= mid) Modify(p << 1, l, mid, s, t, q);
	if(mid < t) Modify(p << 1 | 1, mid + 1, r, s, t, q);
	PushUp(p);
	//cout << p << " " << l << " " << r << '\n';
	//DEBUG(Tree[p]);
}

易错点在于PushDown 时 fl 记得下传，Build 时每个懒标记都要初始化。