链接: https://cses.fi/problemset/task/1723

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑一个有 $n$ 个节点和 $m$ 条边的有向图。你的任务是统计从节点 $1$ 到节点 $n$、恰好经过 $k$ 条边的路径数量。

输入

第一行输入包含三个整数 $n$、$m$ 和 $k$：分别表示节点数、边数和路径长度。节点编号为 $1,2,\dots,n$。

随后有 $m$ 行描述边。每行包含两个整数 $a$ 和 $b$：表示存在一条从节点 $a$ 到节点 $b$ 的边。

输出

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

数据范围

$1 \le n \le 100$ $1 \le m \le n(n-1)$ $1 \le k \le 10^9$ $1 \le a,b \le n$

样例输入

3 4 8
1 2
2 3
3 1
3 2

样例输出

2