#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}

struct poly{
    vector <Z> a;
    poly(int sz):a(sz){}
    poly(){}
    poly(vector<Z>b){a=b;}
};
poly operator +(poly p,poly q){
    if(SZ(p.a) < SZ(q.a)) swap(p,q);
    rep(i,0,SZ(q.a) - 1) p.a[i] += q.a[i];
    return p;
}

poly operator *(poly p,poly q){
    int n = SZ(p.a) - 1,m = SZ(q.a) - 1;
    if(n < 0 || m < 0) return poly(0);
    poly ret(n + m + 1);
    rep(i,0,n){
        rep(j,0,m) ret.a[i + j] += p.a[i] * q.a[j];
    } 
    return ret;
}

poly operator %(poly p,poly q){
    int n = SZ(p.a) - 1,m = SZ(q.a) - 1;
    while(m >= 0 && q.a[m].val() == 0) m--;
    assert(m >= 0);

    Z iv = Z(1) / q.a[m],rr;
    per(i,n,m){
        rr = p.a[i] * iv;
        rep(k,0,m) p.a[i - k] -= rr * q.a[m - k];
    }
    p.a.resize(m);
    return p;
}

void divxk(poly &p,int k){
    int deg = SZ(p.a) - 1;
    while(deg >= 0 && p.a[deg].val() == 0) deg--;
    if(deg < k){
        p.a = vector<Z>({0});
        return;
    }
    rep(i,0,deg - k) p.a[i] = p.a[i + k];
    p.a.resize(deg - k + 1);
}

void prt(poly &p){
    int n = SZ(p.a) - 1;
    printf("(");
    rep(i,0,n) printf("%d ",p.a[i].val());
    printf(")");
}

poly Fmod;
struct Matrix{
    poly v[2][2];
};
Matrix operator *(Matrix p,Matrix q){
/*    printf("Matrix multiply\n");
    rep(i,0,1){
        rep(j,0,1){
            prt(p.v[i][j]);
            printf(" ");
        }
        printf("\n");
    }
    rep(i,0,1){
        rep(j,0,1){
            prt(q.v[i][j]);
            printf(" ");
        }
        printf("\n");
    }*/
    Matrix ans;
    rep(i,0,1){
        rep(j,0,1){
            rep(k,0,1) ans.v[i][j] = ans.v[i][j] + p.v[i][k] * q.v[k][j];
        }
    }
/*    rep(i,0,1){
        rep(j,0,1){
            prt(ans.v[i][j]);
            printf(" ");
        }
        printf("\n");
    }  */
    rep(i,0,1){
        rep(j,0,1) ans.v[i][j] = ans.v[i][j] % Fmod;
    }
/*    rep(i,0,1){
        rep(j,0,1){
            prt(ans.v[i][j]);
            printf(" ");
        }
        printf("\n");
    }  */
    return ans;
}

Matrix power(Matrix p,ll K){
    Matrix ret;
    rep(i,0,1) ret.v[i][i].a.eb(1);
    while(K){
        if(K % 2 == 1) ret = ret * p;
        p = p * p;
        K /= 2;
    }
    return ret;
}

Z res(poly p,poly q){
    int n = SZ(p.a) - 1,m = SZ(q.a) - 1;
    if(!n || !m) return power(p.a[n],m) * power(q.a[m],n);

    if(n > m){
        if(n * m % 2) return -res(q,p);
        return res(q,p);
    }
    poly r = q % p;
    return res(p,r) * power(p.a[n],SZ(q.a) - SZ(r.a));
}

int n,m;
ll K;
Z M[505][505];

Z dp[505][505];
poly Char(){
    rep(i,2,n){
        int pos = -1;
        rep(j,i,n) if(M[j][i - 1].val()) pos = j;
        if(pos == -1) continue;

        rep(k,1,n) swap(M[i][k],M[pos][k]);
        rep(k,1,n) swap(M[k][i],M[k][pos]);

        rep(j,i + 1,n){
            Z rr = M[j][i - 1] / M[i][i - 1];
            rep(k,1,n) M[j][k] -= M[i][k] * rr;
            rep(k,1,n) M[k][i] += M[k][j] * rr; 
        }
    }

    dp[0][0] = 1;
    rep(i,1,n){
        rep(k,1,i) dp[i][k] += dp[i - 1][k - 1];
        rep(k,0,i - 1) dp[i][k] -= M[i][i] * dp[i - 1][k];

        Z prd = 1;
        per(j,i,2){
            prd *= M[j][j - 1];
            rep(k,0,j - 2) dp[i][k] -= prd * M[j - 1][i] * dp[j - 2][k];
        }
    }    
    poly ret(n + 1);
    rep(i,0,n) ret.a[i] = dp[n][i];
    return ret;
}

int main(){
//    freopen("test.in","r",stdin);
    scanf("%d%d%lld",&n,&m,&K);
    rep(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        M[u][u]++;M[v][v]++;M[u][v]--;M[v][u]--;
    }
    poly F = Char();
    rep(i,0,n) if(i % 2 != n % 2) F.a[i] *= -1;
//    rep(i,0,n) printf("%d ",F.a[i].val());
//    printf("\n");
    Z answer = F.a[1] / n;
    Fmod = F;
    Matrix st,nxt;
    st.v[0][0].a.eb(1);
    st.v[0][1].a.eb(-1);st.v[0][1].a.eb(1);

    nxt.v[0][1].a.eb(-1);
    nxt.v[1][0].a.eb(1);
    nxt.v[1][1].a.eb(-2);nxt.v[1][1].a.eb(1);

    st = st * power(nxt,K - 1);
    poly G = st.v[0][0] + st.v[0][1];
    divxk(F,1);divxk(G,1);
/*    rep(i,0,SZ(G.a) - 1) printf("%d ",G.a[i].val());
    printf("\n");
    rep(i,0,SZ(F.a) - 1) printf("%d ",F.a[i].val());
    printf("\n");*/
    answer *= res(F,G);
    if(n % 2 == 0 && K % 2 == 0) answer *= -1;
    printf("%d\n",answer.val());
	return 0;
}