题目描述

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

输入格式

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

输出格式

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

样例输入

1 1
1 0
5 3
3 2

样例输出

4

提示

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