{"raw_statement":[{"iden":"problem statement","content":"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.\nConsider 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$.\nFind each element, modulo $p$, of the sum of $B^p$ over all possible $B$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 100$\n*   $p$ is a prime such that $1 \\leq p \\leq 10^9$.\n*   $0 \\leq A_{i,j} \\leq p-1$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $p$\n$A_{1,1}$ $\\cdots$ $A_{1,N}$\n$\\vdots$\n$A_{N,1}$ $\\cdots$ $A_{N,N}$"},{"iden":"sample input 1","content":"2 3\n0 1\n0 2"},{"iden":"sample output 1","content":"0 2\n1 2\n\n$B^p$ for all possible $B$ are as follows:\n\n*   $\\begin{pmatrix}1&1 \\\\ 1&2\\end{pmatrix}^3=\\begin{pmatrix}5&8 \\\\ 8&13\\end{pmatrix}$\n*   $\\begin{pmatrix}1&1 \\\\ 2&2\\end{pmatrix}^3=\\begin{pmatrix}9&9 \\\\ 18&18\\end{pmatrix}$\n*   $\\begin{pmatrix}2&1 \\\\ 1&2\\end{pmatrix}^3=\\begin{pmatrix}14&13 \\\\ 13&14\\end{pmatrix}$\n*   $\\begin{pmatrix}2&1 \\\\ 2&2\\end{pmatrix}^3=\\begin{pmatrix}20&14 \\\\ 28&20\\end{pmatrix}$\n\nPrint each element, modulo $p=3$, of their sum $\\begin{pmatrix}48&44 \\\\ 67&65\\end{pmatrix}$."},{"iden":"sample input 2","content":"3 2\n1 0 0\n0 1 0\n0 0 1"},{"iden":"sample output 2","content":"1 1 1\n1 1 1\n1 1 1\n\n$B^p$ for all possible $B$ are as follows:\n\n*   $\\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}$\n\nPrint each element, modulo $p=2$, of their sum $\\begin{pmatrix}3&3&3\\\\3&3&3\\\\3&3&3\\end{pmatrix}$."},{"iden":"sample input 3","content":"4 13\n0 1 2 0\n3 4 0 5\n0 6 0 7\n8 9 0 0"},{"iden":"sample output 3","content":"8 0 6 5\n11 1 8 5\n8 0 4 12\n8 0 1 9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}