Path Counting

Problem Description

You are given a directed graph (which may contain multiple edges and self-loops). Count the number of walks that start at vertex $u$, use exactly $k$ edges, and end at vertex $v$. Since the answer may be very large, output it modulo $10^9 + 7$.

Input Format

The first line contains two integers $n, m$, the number of vertices and edges, respectively.

The next $m$ lines each contain two integers $x, y$, indicating a directed edge from $x$ to $y$.

The last line contains three integers $u, v, k$, the query.

Output Format

Output one line containing a single integer: the answer modulo $10^9 + 7$.

Sample Input

2 3
1 2
2 1
1 1
1 2 3

Sample Output

2

Constraints

For $100\%$ of the test cases, $1 \le n \le 200$, $1 \le m \le 10^4$, $1 \le x, y, u, v \le n$, $1 \le k \le 10^9$.