### 问题描述 给定 $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$ 取模。 ### 样例输入 ```text 4 4 4 1 2 2 3 3 4 1 4 ``` ### 样例输出 ```text 8 ``` ### 评测数据规模 对于所有测评数据，$1 \leq K \leq N \leq 10^3,N-1 \leq M \leq N+3$。