{"problem":{"name":"Walk","description":{"content":"There is a simple directed graph $G$ with $N$ vertices, numbered $1, 2, \\ldots, N$. For each $i$ and $j$ ($1 \\leq i, j \\leq N$), you are given an integer $a_{i, j}$ that represents whether there is a ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_r"},"statements":[{"statement_type":"Markdown","content":"There is a simple directed graph $G$ with $N$ vertices, numbered $1, 2, \\ldots, N$.\nFor each $i$ and $j$ ($1 \\leq i, j \\leq N$), you are given an integer $a_{i, j}$ that represents whether there is a directed edge from Vertex $i$ to $j$. If $a_{i, j} = 1$, there is a directed edge from Vertex $i$ to $j$; if $a_{i, j} = 0$, there is not.\nFind the number of different directed paths of length $K$ in $G$, modulo $10^9 + 7$. We will also count a path that traverses the same edge multiple times.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 50$\n*   $1 \\leq K \\leq 10^{18}$\n*   $a_{i, j}$ is $0$ or $1$.\n*   $a_{i, i} = 0$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$a_{1, 1}$ $\\ldots$ $a_{1, N}$\n$:$\n$a_{N, 1}$ $\\ldots$ $a_{N, N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_r","tags":[],"sample_group":[["4 2\n0 1 0 0\n0 0 1 1\n0 0 0 1\n1 0 0 0","6\n\n$G$ is drawn in the figure below:\n![image](https://img.atcoder.jp/dp/paths_0_muffet.png)\nThere are six directed paths of length $2$:\n\n*   $1$ → $2$ → $3$\n*   $1$ → $2$ → $4$\n*   $2$ → $3$ → $4$\n*   $2$ → $4$ → $1$\n*   $3$ → $4$ → $1$\n*   $4$ → $1$ → $2$"],["3 3\n0 1 0\n1 0 1\n0 0 0","3\n\n$G$ is drawn in the figure below:\n![image](https://img.atcoder.jp/dp/paths_1_muffet.png)\nThere are three directed paths of length $3$:\n\n*   $1$ → $2$ → $1$ → $2$\n*   $2$ → $1$ → $2$ → $1$\n*   $2$ → $1$ → $2$ → $3$"],["6 2\n0 0 0 0 0 0\n0 0 1 0 0 0\n0 0 0 0 0 0\n0 0 0 0 1 0\n0 0 0 0 0 1\n0 0 0 0 0 0","1\n\n$G$ is drawn in the figure below:\n![image](https://img.atcoder.jp/dp/paths_2_muffet.png)\nThere is one directed path of length $2$:\n\n*   $4$ → $5$ → $6$"],["1 1\n0","0"],["10 1000000000000000000\n0 0 1 1 0 0 0 1 1 0\n0 0 0 0 0 1 1 1 0 0\n0 1 0 0 0 1 0 1 0 1\n1 1 1 0 1 1 0 1 1 0\n0 1 1 1 0 1 0 1 1 1\n0 0 0 1 0 0 1 0 1 0\n0 0 0 1 1 0 0 1 0 1\n1 0 0 0 1 0 1 0 0 0\n0 0 0 0 0 1 0 0 0 0\n1 0 1 1 1 0 1 1 1 0","957538352\n\nBe sure to print the count modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:14"}}