路径数量统计

题目描述

给你一张有向图，图中可能存在重边和自环，请求出从点 $u$ 出发经过恰好 $k$ 条边后到达点 $v$ 的通路的条数。由于答案可能很大，请输出答案模 $10^9 + 7$。

输入格式

第一行两个整数 $n, m$ 分别表示点数和边数。

接下来 $m$ 行，每行两个整数 $x, y$，表示从 $x$ 到 $y$ 有一条有向边。

最后一行三个整数 $u, v, k$ 表示询问。

输出格式

一行一个数表示答案模 $10^9 + 7$ 的结果。

样例输入

2 3
1 2
2 1
1 1
1 2 3

样例输出

2

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 200, 1\leq m \leq 10^4, 1\leq x,y,u,v \leq n, 1\leq k\leq 10^9$。