{"problem":{"name":"Matrix Pow Sum","description":{"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. Consider a matrix $B$ obtained by r","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc190_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc190_d","tags":[],"sample_group":[["2 3\n0 1\n0 2","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}$."],["3 2\n1 0 0\n0 1 0\n0 0 1","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}$."],["4 13\n0 1 2 0\n3 4 0 5\n0 6 0 7\n8 9 0 0","8 0 6 5\n11 1 8 5\n8 0 4 12\n8 0 1 9"]],"created_at":"2026-03-03 11:01:13"}}