题目背景
翻译自 CSES-1723 题。
题目描述
考虑一个有 n 个节点和 m 条边的有向图。你的任务是计算从节点 1 到节点 n 的路径数量，路径的长度恰好为 k 条边。
输入格式
第一行输入三个整数 n，m，k：分别表示节点数、边数和路径的长度。节点编号为 1,2,…,n。
接下来的 m 行描述了每一条边，每行包含两个整数 a 和 b，表示从节点 a 到节点 b 有一条有向边。
输出格式
输出从节点 1 到节点 n 的路径数量，路径的长度恰好为 k，结果对 109+7 取模。
样例
3 4 8
1 2
2 3
3 1
3 2
2
提示
路径有：
1→2→3→1→2→3→1→2→3
1→2→3→2→3→2→3→2→3
数据范围
- 1≤n≤100
- 1≤m≤n(n−1)
- 1≤k≤109
- 1≤a,b≤n
