题目描述

给定矩阵 $A,B$ 和模数 $p$，求最小的 $x$ 满足 $A^x ≡ B(\mod p)$。

输入格式

第一行两个整数 $n$ 和 $p$，表示矩阵的阶和模数。

接下来一个 $n×n$ 的矩阵 $A$。

接下来一个 $n×n$ 的矩阵 $B$。

输出格式

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

输入数据 1

2 7
1 1
1 0
5 3
3 2

输出数据 1

4

数据范围

对于 $100$ 的数据，$n≤70，p≤19997$，$p$ 为质数，$0≤A_{i,j} ,B_{i,j}< p$，保证 $A$ 有逆。