B3646 数列前缀和 3

给定模质数 $p$ 域上的 $k$ 阶非奇异矩阵列 $a$，给定 $q$ 次询问，每次给出 $l, r$，求 $\prod \limits_{i = l}^r a_i$。$p = 1145141$。 注：模 $p$ 域上的非奇异矩阵指：矩阵乘法加法均在模 $p$ 下进行，矩阵（在实数域下）的行列式值对 $p$ 取余不为 $0$。

无

无

### 样例 1 解释 $a_1 = \begin{pmatrix} 2 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{pmatrix}$，$a_2 = \begin{pmatrix} 2 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{pmatrix}$，$a_3 = \begin{pmatrix} 20 & 20 & 21 \\ 22 & 23 & 24 \\ 25 & 26 & 27\end{pmatrix}$。 $a_1 \times a_2 = \begin{pmatrix} 33 & 38 & 45 \\ 70 & 81 & 96 \\ 109 & 126 &150 \end{pmatrix}$，$a_2 \times a_3 = \begin{pmatrix}159 & 164 & 171 \\ 340 & 351 & 366 \\ 541 & 558& 582 \end{pmatrix}$，$a_1 \times a_2 \times a_3 = \begin{pmatrix}2621 &2704& 2820 \\ 5582 & 5759 & 6006 \\ 8702 & 8978 & 9363 \end{pmatrix}$。 所有数字的按位异或和为 $14921$。 ### 数据规模与约定 对于全部的测试点，保证 $1 \leq n, q \leq 10^6$，$2 \leq k \leq 3$，$1 \leq l \leq r \leq n$，矩阵元素均为小于 $p$ 的正整数。