{"raw_statement":[{"iden":"problem statement","content":"Maroon came up with the following problem:\n\n* * *\n\nSnuke has an integer sequence $a$ of length $N$. Initially, $a_i=0$ for every $i$ ($1 \\leq i \\leq N$).\nSnuke will repeat the following two operations any number of times in any order:\n\n*   Operation $1$: Replace $a_i$ with $a_i+x$, where $i$ ($1 \\leq i \\leq N$) and $x$ ($x=1$ or $x=-1$) are integers of his choice. The cost of doing this operation once is $1$.\n    \n*   Operation $2$: Replace $a_i$ with $a_i+x$ for every $i$ ($l \\leq i \\leq r$), where $l$, $r$ ($1 \\leq l \\leq r \\leq N$) and $x$ ($x=1$ or $x=-1$) are integers of his choice. The cost of doing this operation once is $C$.\n    \n\nYou are given an integer sequence $A$ of length $N$. Snuke wants to make $a_i=A_i$ for every $i$. Find the minimum total cost needed to achieve his objective.\n\n* * *\n\nHowever, during the preparation of this problem, too many unexpected solutions were found, so Maroon changed the problem into the following:\n\n* * *\n\nSnuke has $N$ integer sequences $B_1,B_2,\\cdots,B_N$ and integers $C$ and $K$. The length of every sequence $B_i$ ($1 \\leq i \\leq N$) is $K$.\nNow, he wants to make an integer sequence $A$ of length $N$ and find the answer to the problem above. The value of $A_i$ will be chosen from $B_{i,1},B_{i,2},\\cdots,B_{i,K}$. Here, even if there are duplicated values in $B_{i,1},B_{i,2},\\cdots,B_{i,K}$, we still distinguish those values. That is, there are $K^N$ ways to make $A$.\nFind the sum of the answers to the problem above over all the ways to make $A$, modulo $(10^9+7)$.\n\n* * *\n\nSolve this problem."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 50$\n*   $1 \\leq C \\leq N$\n*   $1 \\leq K \\leq 50$\n*   $1 \\leq B_{i,j} \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $C$ $K$\n$B_{1,1}$ $B_{1,2}$ $\\cdots$ $B_{1,K}$\n$B_{2,1}$ $B_{2,2}$ $\\cdots$ $B_{2,K}$\n$\\vdots$\n$B_{N,1}$ $B_{N,2}$ $\\cdots$ $B_{N,K}$"},{"iden":"sample input 1","content":"5 2 1\n2\n3\n1\n2\n1"},{"iden":"sample output 1","content":"6\n\nWe have $A=(2,3,1,2,1)$. Below is one optimal sequence of operations:\n\n*   Let $l=1,r=5,x=1$ and do Operation $2$, resulting in $a=(1,1,1,1,1)$.\n*   Let $l=1,r=4,x=1$ and do Operation $2$, resulting in $a=(2,2,2,2,1)$.\n*   Let $i=2,x=1$ and do Operation $1$, resulting in $a=(2,3,2,2,1)$.\n*   Let $i=3,x=-1$ and do Operation $1$, resulting in $a=(2,3,1,2,1)$."},{"iden":"sample input 2","content":"3 2 3\n1 2 3\n1 2 3\n1 2 3"},{"iden":"sample output 2","content":"126"},{"iden":"sample input 3","content":"10 4 1\n8\n10\n10\n1\n5\n9\n5\n5\n9\n1"},{"iden":"sample output 3","content":"45"},{"iden":"sample input 4","content":"10 5 10\n79 48 35 56 16 26 37 6 75 23\n39 99 57 100 49 90 18 9 12 91\n29 97 49 86 30 94 78 63 49 22\n100 27 48 91 66 14 6 20 23 84\n12 60 99 75 88 95 61 58 20 46\n10 11 30 38 55 94 9 52 92 75\n27 22 46 85 83 88 50 63 95 91\n49 59 19 37 53 27 11 26 2 91\n95 36 20 76 84 41 59 95 67 66\n52 60 17 11 28 57 75 69 95 24"},{"iden":"sample output 4","content":"877826779"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}