AT_arc190_d [ARC190D] Matrix Pow Sum

素数 $ p $ と $ N\times N $ 行列 $ A = (A_{i,j}) $ ( $ 1\leq i,j\leq N $ ) が与えられます． $ A $ の成分は $ 0 $ 以上 $ p-1 $ 以下の整数です． $ A $ の成分のうち， $ 0 $ を全て $ 1 $ 以上 $ p-1 $ 以下の整数に置き換えて得られる行列 $ B $ は， $ A $ に含まれる $ 0 $ の個数を $ K $ とすると $ (p-1)^K $ 個あります． 考えられる $ B $ 全てに対する $ B^p $ の総和の各成分を $ p $ で割った余りを求めてください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ p $ $ A_{1,1} $ $ \cdots $ $ A_{1,N} $ $ \vdots $ $ A_{N,1} $ $ \cdots $ $ A_{N,N} $

$ N $ 行出力してください． $ i $ 行目には $ j=1,\ldots,N $ の順に，考えられる $ B $ 全てに対する $ B^p $ の総和の $ (i,j) $ 成分を $ p $ で割った余りを空白区切りで出力してください．

### Sample Explanation 1 考えられる $ B $ 全てに対する $ B^p $ は次の通りです． - $ \begin{pmatrix}1&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}5&8 \\ 8&13\end{pmatrix} $ - $ \begin{pmatrix}1&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}9&9 \\ 18&18\end{pmatrix} $ - $ \begin{pmatrix}2&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}14&13 \\ 13&14\end{pmatrix} $ - $ \begin{pmatrix}2&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}20&14 \\ 28&20\end{pmatrix} $ これらの総和 $ \begin{pmatrix}48&44 \\ 67&65\end{pmatrix} $ の各成分を $ p=3 $ で割った余りを出力します． ### Sample Explanation 2 考えられる $ B $ 全てに対する $ B^p $ は次の通りです． - $ \begin{pmatrix}1&1&1 \\ 1&1&1 \\ 1&1&1\end{pmatrix}^2=\begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix} $ これらの総和 $ \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix} $ の各成分を $ p=2 $ で割った余りを出力します． ### Constraints - $ 1\leq N\leq 100 $ - $ p $ は $ 1\leq p\leq 10^9 $ を満たす素数 - $ 0\leq A_{i,j}\leq p-1 $ - 入力される値はすべて整数である