题目描述

给定矩阵 $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$ 有逆。