### 问题描述

给定 $N$ 个点 $M$ 条边的无向联通图和定值 $K$，保证图中没有重边和自环，求解图中长度为 $K$ 的简单路径的个数，答案对 $10^9+7$ 取模。

无向图中一个有序点集 $(i_1,i_2,...,i_k)$ 被称为简单路径当且仅当 $i_1,i_2,...,i_k$ 两两不同，且图中存在边 $(i_1,i_2),(i_2,i_3),...,(i_{k-1},i_k)$。

简单路径的长度定义为简单路径经过的节点个数。

输入格式

第一行包含 $2$ 个正整数 $N,M,K$，表示无向图中的点数和边数以及参数 $K$。

之后 $M$ 行，每行给定 $2$ 个正整数 $u_i,v_i$，表示图中的一条无向边 $(u_i,v_i)$。

输出格式

输出一行，包含一个整数，表示答案，答案对 $10^9+7$ 取模。

样例输入

4 4 4
1 2
2 3
3 4
1 4

样例输出

8

评测数据规模

对于所有测评数据，$1 \leq K \leq N \leq 10^3,N-1 \leq M \leq N+3$。