CSES1723 图的路径 I
#CS1723. 图的路径 I
图的路径 I
题目背景
翻译自 CSES-1723 题。
题目描述
考虑一个有 n 个节点和 m 条边的有向图。你的任务是计算从节点 1 到节点 n 的路径数量，路径的长度恰好为 k 条边。
输入格式
第一行输入三个整数 n，m，kn，m，kn，m，k：分别表示节点数、边数和路径的长度。节点编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来的 m 行描述了每一条边，每行包含两个整数 a 和 b，表示从节点 a 到节点 b 有一条有向边。
输出格式
输出从节点 1 到节点 n 的路径数量，路径的长度恰好为 k，结果对 109+710^9+7109+7 取模。
样例
3 4 8
1 2
2 3
3 1
3 2
2
样例1解释 路径有：
1→2→3→1→2→3→1→2→31 → 2 → 3 → 1 → 2 → 3 → 1 → 2 → 31→2→3→1→2→3→1→2→3
1→2→3→2→3→2→3→2→31 → 2 → 3 → 2 → 3 → 2 → 3 → 2 → 31→2→3→2→3→2→3→2→3
说明/提示