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 $s$ to vertex $t$, modulo $10^9 + 7$. A path can visit the same vertex or edge multiple times.
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.
For each query, print a line with the answer modulo $1000000007$.
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$:
## Input
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.
## Output
For each query, print a line with the answer modulo $1000000007$.
[samples]
## Note
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$
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, $ |E| = m $.
Let $ 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.
**Constraints**
1. $ 1 \le n, q \le 200 $
2. $ 0 \le m \le n(n-1) $
3. No self-loops: $ A_{i,i} = 0 $ for all $ i $
4. No multiple edges
5. For each query: $ 1 \le s, t \le n $, $ 1 \le k \le 10^9 $
**Objective**
For each query $ (s, t, k) $, compute:
$$
(A^k)_{s,t} \mod 10^9 + 7
$$