分析：
首先，对于任意一个不在双联通分量内的边，其选任意颜色都可以。
对于仅存在于一个不相交的环上的边，根据polya定理，其方案数即为：
∑i≤ni=1kgcd(i,n)n（n为边数，k为颜色数）∑i=1i≤nkgcd(i,n)n（n为边数，k为颜色数）
其实这两种情况处理方案是一样的。。。（第一种即n=1的情况）
对于第三种情况，即多个环相交时，有一个很神奇的结论：任意两条边的颜色，可以通过不同环的旋转进行交换。
证明只会画图。。。随便分几个类画几个图就能发现，，似乎是这样。
所以这部分当且仅当某个颜色数量不同，才视为不同方案。
方案数就是
Ck?1n+k?1Cn+k?1k?1
判断一个边是单环还是多环，可以通过tarjan存边时，顺便存一个点，如果这某个点在退栈的过程中，如果多次访问到某个点，则表明这是一个多环。否则就是一个单环。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MOD 1000000007
using namespace std;
typedef long long ll;
vector<int> a[MAXN],id[MAXN];
int vis[MAXN];
int n,m,k,cnt;
int dfn[MAXN],low[MAXN];
ll mi[MAXN],inv[MAXN],fac[MAXN],ans=1ll;
ll fsp(ll x,int y){ll res=1;while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1; }return res;
}
ll C(int n,int m){return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int gcd(int x,int y){if(y==0)return x;return gcd(y,x%y);
}
int s[MAXN],s1[MAXN],top,used[MAXN];
void dfs(int x){dfn[x]=low[x]=++cnt;for(int i=0;i<a[x].size();i++){if(vis[id[x][i]]==1)continue;int u=a[x][i];s[++top]=id[x][i];vis[id[x][i]]=1;s1[top]=x;if(dfn[u]==0){dfs(u);low[x]=min(low[x],low[u]);if(low[u]>=dfn[x]){bool flag=1;int tot=0;for(int j=top;s[j+1]!=id[x][i];j--){if(used[s1[j]]==1)flag=0;tot++;used[s1[j]]=1;}if(flag){ll res=0;for(int j=1;j<=tot;j++){res+=mi[gcd(j,tot)];res%=MOD;}res*=fsp(tot,MOD-2);res%=MOD;ans*=res;ans%=MOD;}else{ans=ans*C(tot+k-1,k-1)%MOD;}//PF("|{
%d:",x);for(;s[top+1]!=id[x][i];top--){used[s1[top]]=0;//PF("%d(%d) ",s1[top],s[top]);}// PF("|[%d]\n",top);}}elselow[x]=min(low[x],dfn[u]);}
}
int main(){SF("%d%d%d",&n,&m,&k);int u,v;for(int i=1;i<=m;i++){SF("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);id[u].push_back(i);id[v].push_back(i);}fac[0]=1ll;mi[0]=1ll;for(int i=1;i<=MAXN-10;i++){fac[i]=fac[i-1]*i%MOD;mi[i]=mi[i-1]*k%MOD;}inv[MAXN-10]=fsp(fac[MAXN-10],MOD-2);for(int i=MAXN-10;i>=1;i--)inv[i-1]=inv[i]*i%MOD;for(int i=1;i<=n;i++)if(dfn[i]==0)dfs(i);PF("%lld",ans);
}