Graph Paths I

题目描述

考虑一个有向图，包含 n 个节点和 m 条边。你的任务是计算从节点 1 到节点 n 恰好有 k 条边的路径数量。

输入格式

第一行输入包含三个整数 n、m 和 k：节点数、边数以及路径长度。节点编号为 1,2,$\dots$,n。 接下来有 m 行描述边。每行包含两个整数 a 和 b：存在一条从节点 a 到节点 b 的边。

输出格式

输出路径数量对 $10^9+7$ 取模的结果。

3 4 8
1 2
2 3
3 1
3 2

2

提示

$1 \le n \le 100$ $1 \le m \le n(n-1)$ $1 \le k \le 10^9$ $1 \le a,b \le n$ 样例解释：路径为 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。

标签: CSES1723|数学

来源

CSES1723|数学