Problem Description

A country with $n$ cities numbered $1,2,\dots,n$ is connected by $m$ two-way roads. There are at most $10$ more roads than the number of cities, but it is still possible to travel between any two cities using one or more roads.

A tourist is planning a journey in the country. They have decided the following:

• The journey will start in city $1$ and end in city $n$.
• The journey should consist of exactly $k$ steps, each traveling one road.
• It is not allowed to travel back and forth along the same road in two consecutive steps. It is possible, however, to travel the same road multiple times if there are other steps in between.

How many possible journey plans are there, traveling from city $1$ to city $n$ in $k$ steps? Two plans are different if they go to different cities at any step.

Input Format

The first line contains three integers $n$, $m$ and $k$: the number of cities and roads in the country, as well as the number of steps in the tourist's journey.

The following $m$ lines describe the roads. Each line contains two distinct integers $u$ and $v$, meaning that there is a road between city $u$ and city $v$. There is at most one road between two cities.

Output Format

Print the number of different journey plans. Since the answer may be large, print it modulo $10^9+7$.

4 5 5
1 2
1 3
2 3
2 4
3 4

4

4 3 4
1 2
2 3
2 4

0

Hint

Explanation 1

The cities and roads of the country are shown in the figure below.

:::align{center} :::

The possible journey plans are:

• $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$
• $1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$
• $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 4$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4$

Explanation 2

There is no valid journey plan with $4$ steps. Note that the plan $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$ is invalid because it uses the road between cities $2$ and $3$ in two consecutive steps.

Constraints

• $2 \le n \le 2 \cdot 10^5$
• $n-1 \le m \le n + 10$
• $1 \le k \le 10^4$

Scoring