#P4128. Matrix

Matrix

题目描述

给定矩阵 AA,BB 和模数 pp,求最小的 xx 满足:

Ax≡B(modp)A^x \equiv B \pmod{p}

输入格式

第一行包含两个整数 nn 和 pp,表示矩阵的阶和模数。

接下来是一个 n×nn \times n 的矩阵 AA。

再接下来是一个 n×nn \times n 的矩阵 BB。

输出格式

输出一个正整数,表示最小的可能的 xx,数据保证在 pp 内有解。

输入样例

2 7
1 1
1 0
5 3
3 2

输出样例

4

提示

对于100%100\%的数据,n≤70n \le 70,p≤19997p \le 19997,pp为质数,0≤Aij,Bij<p0 \le A_{ij},B_{ij} < p,保证 AA 有逆。