AT_arc190_d [ARC190D] Matrix Pow Sum

You are given a prime number $ p $ and an $ N \times N $ matrix $ A = (A_{i,j}) $ ( $ 1\leq i,j\leq N $ ). Each element of $ A $ is an integer between $ 0 $ and $ p-1 $ , inclusive. Consider a matrix $ B $ obtained by replacing each zero in $ A $ with an integer between $ 1 $ and $ p-1 $ , inclusive. There are $ (p-1)^K $ such matrices $ B $ , where $ K $ is the number of zeros in $ A $ . Find each element, modulo $ p $ , of the sum of $ B^p $ over all possible $ B $ .

The input is given from Standard Input in the following format: > $ N $ $ p $ $ A_{1,1} $ $ \cdots $ $ A_{1,N} $ $ \vdots $ $ A_{N,1} $ $ \cdots $ $ A_{N,N} $

Print $ N $ lines. The $ i $ -th line should contain, in the order $ j=1,\ldots,N $ , the $ (i,j) $ element of the sum, modulo $ p $ , of $ B^p $ over all possible $ B $ , separated by spaces.

### Sample Explanation 1 $ B^p $ for all possible $ B $ are as follows: - $ \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} $ Print each element, modulo $ p=3 $ , of their sum $ \begin{pmatrix}48&44 \\ 67&65\end{pmatrix} $ . ### Sample Explanation 2 $ B^p $ for all possible $ B $ are as follows: - $ \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} $ Print each element, modulo $ p=2 $ , of their sum $ \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix} $ . ### Constraints - $ 1 \leq N \leq 100 $ - $ p $ is a prime such that $ 1 \leq p \leq 10^9 $ . - $ 0 \leq A_{i,j} \leq p-1 $ - All input values are integers.