7401. 图上路径 I (Graph Paths I)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 图上路径 I (Graph Paths I) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 考虑一个包含 $n$ 个节点和 $m$ 条有向边的有向图。您的任务是计算从节点 $1$ 出发，且恰好包含 $k$ 条有向边的到达节点 $n$ 的路径数量。 ## 输入格式 第一行包含三个整数 $n$、$m$ 和 $k$：分别代表节点的数量、边的数量以及路径中的边数。节点从 $1, 2, \dots, n$ 编号。 接下来有 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示存在一条从节点 $a$ 指向节点 $b$ 的有向边。 ## 输出格式 输出对应路径的数量，结果对 $10^9+7$ 取模。 ## 输入输出样例 ### 输入 #1 ```text 3 4 8 1 2 2 3 3 1 3 2 ``` ### 输出 #1 ```text 2 ``` ## 说明/提示 在样例中，满足要求的两条路径分别为： - $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3$ - $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3$ ### 数据规模与约定 - $1 \le n \le 100$ - $1 \le m \le n(n-1)$ - $1 \le k \le 10^9$ - $1 \le a, b \le n$ ---