{"problem":{"name":"D. Count Paths","description":{"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 sa","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264D"},"statements":[{"statement_type":"Markdown","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## Input\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.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.\n\n## Output\n\nPrint 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.  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$","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}