{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For each query, print a line with the answer modulo $1000000007$."},{"iden":"note","content":"In 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$ "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"Given a directed graph with n vertices and m edges, answer q queries: for each query (s, t, k), count the number of paths of exactly k edges from vertex s to vertex t, modulo 10^9 + 7. You can revisit vertices and edges.","has_page_source":false}