/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/*
 * @Description: I want to be the weakest vegetable in the world!
 * @Author: I.Z.
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD         1000000007
#define speMOD      2933256077ll
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
mt19937 sd(random_device{}());
int qpow(int a,int b,int m=MOD,int res=1){
	a%=m;
	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
	return res;
}
int exgcd(int x,int y,int &a,int &b){
	if(y==0){
		a=1;b=0;
		return x;
	}
	int d=exgcd(y,x%y,a,b);
	int z=b;
	b=a-b*(x/y);
	a=z;
	return d;
}
int _x_,_y_;
inline int inverse(int x,int y=MOD){
	exgcd(x,y,_x_,_y_);
	return (_x_+y)%y;
}
int fac[2000005],inv[2000005];
void init(int n){
	fac[0]=inv[0]=1;
	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
	inv[n]=qpow(fac[n],MOD-2);
	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int binom(int x,int y){
	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
int n,m,k;
int s1[20],s2[20];
int f[100000][20],F[100005];
int g[100000][20];
int S[100005],S1[100005];
int dp[20][20];
void Main() {
	cin>>n>>m>>k;
	dp[0][0]=1;
	REP(i,0,k){
		REP(j,0,n+1)if(dp[i][j]){
			(dp[i+1][j]+=dp[i][j]*(j+2))%=MOD;
			(dp[i+1][j+1]+=dp[i][j]*(n+i+1-j-2))%=MOD;
		}
	}
	REP(i,0,m){
		int x,y;
		cin>>x>>y;
		--x,--y;
		s1[x]|=(1<<y);
		s2[y]|=(1<<x);
	}
	REP(i,1,(1<<n)){
		int x=__builtin_ctz(i);
		S[i]=S[i^(1<<x)]|s1[x]|s2[x];
		S1[i]=S1[i^(1<<x)]|s1[x];
	}
	F[0]=1;
	REP(i,1,(1<<n)){
		REP(j,0,n)if((i>>j)&1){
			if(!(s1[j]&i))F[i]+=F[i^(1<<j)];
		}
		F[i]%=MOD;
	}
	f[0][0]=1;
	REP(i,1,(1<<n)){
		int x=__builtin_ctz(i);
		for(int j=i;j;j=(j-1)&i)if((j>>x)&1){
			if(S[j]&(j^i))continue;
			REP(l,0,cntbit(i)){
				(f[i][l+1]+=f[i^j][l]*F[j])%=MOD;
			}
		}
	}
	g[0][0]=1;
	REP(i,1,(1<<n)){
		for(int j=i;j;j=(j-1)&i)if(!(S1[j]&(i^j))){
			int n1=cntbit(j),n2=cntbit(i)-cntbit(j);
			REP(l,1,n1+1)if(f[j][l]){
				REP(p,0,n2+1)if(g[i^j][p]){
					(g[i][l+p]+=(l&1? 1:-1)*g[i^j][p]*f[j][l])%=MOD;
				}
			}
		}
	}
	init(100);
	int ans=0;
	REP(i,1,n+1)if(g[(1<<n)-1][i]){
		int co=0;
		REP(j,0,i){
			//有几个位置不让选，一共 i-1 个位置
			int c=binom(i-1,j)*fac[i-j+1+k-1]%MOD*inv[i-j]%MOD;
			if(j&1)co-=c;else co+=c;
		}
		co%=MOD;(co*=fac[i])%=MOD;
		(ans+=co*g[(1<<n)-1][i])%=MOD;
	}
	(ans*=inv[k+n])%=MOD;
	(ans+=MOD)%=MOD;
	over(ans)
}
void TC() {
    int tc=1;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */