{"problem":{"name":"I. Count Paths Queries","description":{"content":"You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges. You need to answer $q$ queries: given $s, t, k$, count paths consisting of $k$ steps (edges) from vertex $","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264I"},"statements":[{"statement_type":"Markdown","content":"You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges.\n\nYou need to answer $q$ queries: given $s, t, k$, count paths consisting of $k$ steps (edges) from vertex $s$ to vertex $t$, modulo $10^9 + 7$. A path can visit the same vertex or edge multiple times.\n\nThe first line contains three integers $n$, $m$ and $q$ ($1 <= n, q <= 200$, $0 <= m <= n dot.op (n -1)$) — respectively the number of vertices, edges and queries.\n\nThe following $m$ lines describe edges. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n, a_i eq.not b_i$), denoting a directed edge from $a_i$ to $b_i$. There are no self-loops or multiple edges.\n\nThe following $q$ lines describe queries. Each line contains three integers $s$, $t$ and $k$ ($1 <= s, t <= n$, $1 <= k <= 10^9$) — the start and end of a path, and its length in edges.\n\nFor each query, print a line with the answer modulo $1000000007$.\n\nIn the first sample test, we are given the following graph with $n = 3$ vertices and $m = 4$ edges.\n\nIn the first query, there are 2 paths of length $k = 6$ from vertex $1$ to vertex $2$:\n\n## Input\n\nThe first line contains three integers $n$, $m$ and $q$ ($1 <= n, q <= 200$, $0 <= m <= n dot.op (n -1)$) — respectively the number of vertices, edges and queries.The following $m$ lines describe edges. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n, a_i eq.not b_i$), denoting a directed edge from $a_i$ to $b_i$. There are no self-loops or multiple edges.The following $q$ lines describe queries. Each line contains three integers $s$, $t$ and $k$ ($1 <= s, t <= n$, $1 <= k <= 10^9$) — the start and end of a path, and its length in edges.\n\n## Output\n\nFor each query, print a line with the answer modulo $1000000007$.\n\n[samples]\n\n## Note\n\nIn the first sample test, we are given the following graph with $n = 3$ vertices and $m = 4$ edges.  In the first query, there are 2 paths of length $k = 6$ from vertex $1$ to vertex $2$:  $1 arrow.r 2 arrow.r 3 arrow.r 1 arrow.r 2 arrow.r 1 arrow.r 2$  $1 arrow.r 2 arrow.r 1 arrow.r 2 arrow.r 3 arrow.r 1 arrow.r 2$","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq V \\times V $, $ |E| = m $.  \nLet $ A \\in \\{0,1\\}^{n \\times n} $ be the adjacency matrix of $ G $, where $ A_{i,j} = 1 $ if there is a directed edge from $ i $ to $ j $, and $ 0 $ otherwise.  \n\n**Constraints**  \n1. $ 1 \\le n, q \\le 200 $  \n2. $ 0 \\le m \\le n(n-1) $  \n3. No self-loops: $ A_{i,i} = 0 $ for all $ i $  \n4. No multiple edges  \n5. For each query: $ 1 \\le s, t \\le n $, $ 1 \\le k \\le 10^9 $  \n\n**Objective**  \nFor each query $ (s, t, k) $, compute:  \n$$\n(A^k)_{s,t} \\mod 10^9 + 7\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}