The Hundred-Step Walk

HH has a peculiar habit: after every meal, he takes a walk, which he calls the Hundred-Step Walk. Each walk is defined as a sequence of moves along the roads of his school campus, where every road has a length of \(1\). However, HH never immediately retraces his last step; that is, if he just walked from node \(u\) to node \(v\), he will not walk directly back from \(v\) to \(u\) on his next move. Because HH loves variety, his daily path is never exactly the same, and he wonders how many distinct walks he can take.

You are given a map of the campus as an undirected graph. Each road connects two locations and has an equal length of \(1\). Given two locations \(A\) and \(B\) and an integer \(t\) representing the number of steps, determine the number of distinct walks of exactly \(t\) steps from \(A\) to \(B\) such that the walk never immediately reverses direction. Since the answer can be extremely large, output the count modulo \(10^9+7\).

Note: A move from \(u\) to \(v\) is allowed as long as \(v\) is adjacent to \(u\) and \(v\) is not the vertex you just came from.

inputFormat

The input consists of multiple lines:

1. The first line contains five integers: \(n\), \(m\), \(t\), \(A\), and \(B\), where \(n\) is the number of nodes, \(m\) is the number of roads (edges), \(t\) is the number of steps, and \(A\) and \(B\) are the start and destination nodes respectively. The nodes are numbered from 1 to \(n\).
2. The next \(m\) lines each contain two integers \(u\) and \(v\) indicating an undirected road connecting node \(u\) and node \(v\).

It is guaranteed that the graph is undirected and there are no duplicate roads.

outputFormat

Output a single integer: the number of valid walks of exactly \(t\) steps from \(A\) to \(B\), taken modulo \(10^9+7\).

sample

3 3 2 1 3
1 2
2 3
1 3

1