题目描述

给定矩阵 $A,B$ 和模数 $p$，求最小的 $x$ 满足 $A^x\equiv B\pmod p$。

输入格式

第一行两个整数 $n$ 和 $p$，表示矩阵的阶和模数，接下来一个 $n\times n$ 的矩阵 $A$，接下来一个 $n\times n$ 的矩阵 $B$。

输出格式

输出一个正整数，表示最小的可能的 $x$，数据保证在 $p$ 内有解。

2 7
1 1
1 0
5 3
3 2

4

数据范围

对于 $100\%$ 的数据，$n\le 70$，$p\le 19997$，$p$ 为质数，$0\le A_{ij},B_{ij} < p$，保证 $A$ 有逆。