题目背景

翻译自 CSES-1723 题。

题目描述

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

输入格式

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

接下来的 $m$ 行描述了每一条边，每行包含两个整数 $a$ 和 $b$，表示从节点 $a$ 到节点 $b$ 有一条有向边。

输出格式

输出从节点 $1$ 到节点 $n$ 的路径数量，路径的长度恰好为 $k$，结果对 $10^9+7$ 取模。

样例

3 4 8
1 2
2 3
3 1
3 2

2

样例1解释

路径有：

$1 → 2 → 3 → 1 → 2 → 3 → 1 → 2 → 3$

$1 → 2 → 3 → 2 → 3 → 2 → 3 → 2 → 3$

说明/提示

$1 \leq n \leq 100$；

$1 \leq m \leq n(n-1)$；

$1 \leq k \leq 10^9$；

$1 \leq a,b \leq n$。