#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head



struct Mod{
  unsigned n;
  Mod() : n(0){}
  Mod( ll x ){
    if( x < 0 ) n = x%MOD+MOD;
    else n = x%MOD;
  }
};
Mod operator + ( Mod a  , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a  , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a  , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
  Mod res = 1;
  while( k ){
    if( k & 1 ) res *= x;
    k /= 2;
    x *= x;
  }
  return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
  ll d = a;
  if( b != 0 ){
    d = extgcd( b , a % b , y , x );
    y -= a / b * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
Mod operator / ( Mod a  , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }



struct Factorial{
  vector<Mod> v;
  Factorial( int max_n ){
    v = vector<Mod>( max_n , 1 );
    FOR( i , 1 , max_n ) v[i] = v[i-1] * i;
  }
  int size(){
    return v.size();
  }
  Mod operator [] ( int id ){
    return v.at(id);
  }
};

struct Factorial_inv{
  vector<Mod> v;
  Factorial_inv( Factorial &f ){
    v = vector<Mod>( f.size() );
    REP( i , f.size() ) v[i] = inv( f[i] );
  }
  Mod operator [] ( int id ){
    return v.at(id);
  }
};

struct Combination{
  Factorial *f;
  Factorial_inv *finv;
  Combination( Factorial &arg_f , Factorial_inv &arg_finv ){
    f = &arg_f;
    finv = &arg_finv;
  }
  Mod operator () ( int a , int b ){
    return (*f)[a] * (*finv)[b] * (*finv)[a-b];
  }
};

Factorial fact( 100010 );
Factorial_inv finv( fact );
Combination comb( fact , finv );


struct BiconnectedComponent{
  int n, m;
  vi dep, low, used;
  vector<vpi> G;
  int cnt;
  vi cmp;
  void init( int size ){
    n = size;
    m = 0;
    G = vector<vpi>( n , vpi(0) );
  }
  void add_edge( int a , int b ){
    G[a].pb( b , m );
    G[b].pb( a , m );
    m++;
  }
  void use( int x , int r ){
    used[x] = cnt;
    YYS( w , G[x] ){
      if( w.fi == r or used[w.fi] == cnt ){
	cmp[w.se] = cnt;
      } else if( used[w.fi] == -2 ){
	cmp[w.se] = cnt;
	use( w.fi , r );
      }
    }
  }
  void dfs( int x , int p = -1 , int d = 0 ){
    used[x] = -2;
    dep[x] = low[x] = d;
    YYS( w , G[x] ){
      if( used[w.fi] == -1 ){
	dfs( w.fi , x , d+1 );
	if( low[w.fi] >= dep[x] ){
	  use( w.fi , x );
	  cnt++;
	}
	chmin( low[x] , low[w.fi] );
      } else if( w.fi != p ){
	chmin( low[x] , dep[w.fi] );
      }
    }
  }
  int bc(){
    used = dep = low = vi( n , -1 );
    cmp = vi( m , -1 );
    cnt = 0;
    REP( i , n ){
      if( used[i] == -1 ){
	dfs( i );
      }
    }
    return cnt;
  }
} bc;



int n, m, k;

vpi edges;

int cmpsz[110];
bool adj[110][50];
bool cycle[110];

int main(){

  n = in();
  m = in();
  k = in();

  bc.init( n );
  REP( i , m ){
    int a = in() - 1;
    int b = in() - 1;
    edges.pb( a , b );
    bc.add_edge( a , b );
  }

  int csz = bc.bc();


  REP( i , m ){
    cmpsz[ bc.cmp[i] ]++;
    adj[ bc.cmp[i] ][ edges[i].fi ] = true;
    adj[ bc.cmp[i] ][ edges[i].se ] = true;
  }

  REP( i , csz ){
    int cnt = 0;
    REP( j , n ){
      if( adj[i][j] ){
        cnt++;
      }
    }
    if( cnt == cmpsz[i] ){
      cycle[i] = true;
    }
  }
  
  Mod ans = 1;
  REP( i , csz ){
    if( cmpsz[i] == 1 ){
      ans *= k;
      // cout << "A" << endl;
    } else if( cycle[i] ){
      Mod cur = 0;
      REP( j , cmpsz[i] ){
        cur += modpow( k , __gcd( (int)j , cmpsz[i] ) );
      }
      // cout << cur.n << endl;
      ans *= cur / cmpsz[i];
    } else {
      // cout << cmpsz[i] << endl;
      ans *= comb( cmpsz[i] + k - 1 , k - 1 );
    }
  }

  printf( "%d\n" , (int)ans.n );
  
  return 0;
}


Measured memory_bytes: 1024