{"raw_statement":[{"iden":"statement","content":"You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges. Count paths consisting of $k$ steps (edges) and print the answer 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 $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 10^9$) — the number of vertices, the number of edges and the length of a path.\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\nPrint 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\nThere are 5 paths of length $k = 2$:\n\n"},{"iden":"input","content":"The first line contains three integers $n$, $m$ and $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 10^9$) — the number of vertices, the number of edges and the length of a path.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."},{"iden":"output","content":"Print the answer modulo $1000000007$."},{"iden":"examples","content":"Input3 4 2\n1 2\n2 3\n3 1\n2 1\nOutput5\nInput5 10 11\n2 3\n4 2\n2 1\n2 4\n1 5\n5 2\n3 2\n3 1\n3 4\n1 2\nOutput21305\n"},{"iden":"note","content":"In the first sample test, we are given the following graph with $n = 3$ vertices and $m = 4$ edges.  There are 5 paths of length $k = 2$:  $1 arrow.r 2 arrow.r 1$  $1 arrow.r 2 arrow.r 3$  $2 arrow.r 1 arrow.r 2$  $2 arrow.r 3 arrow.r 1$  $3 arrow.r 1 arrow.r 2$ "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of player skill levels.  \nLet $ B = (b_1, b_2, \\dots, b_k) $ be a sequence of position weights.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^3 $  \n2. $ 1 \\leq k \\leq n $  \n3. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\leq b_j \\leq 10^5 $ for all $ j \\in \\{1, \\dots, k\\} $  \n\n**Objective**  \nSelect a strictly increasing sequence of indices $ 1 \\leq i_1 < i_2 < \\dots < i_k \\leq n $ to maximize:  \n$$\n\\sum_{j=1}^{k} a_{i_j} \\cdot b_j\n$$","simple_statement":"Timmy has n players in a line, each with skill a_i. He must pick exactly k players in order, and the j-th picked player contributes a_i * b_j to the total. Find the maximum possible total.","has_page_source":false}