#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1'000'000'007;
const int maxn=20;
int n,m,k;
int par[maxn]; 
vector<int>adj[maxn];
vector<int>tadj[maxn];
int in[maxn];
int sz[maxn];
int F[maxn];
int col[maxn];
bool bad=0;
void check(int x){
	if(col[x] == 2){
		bad=1;
		return;
	}
	if(col[x] == 1)return;
	col[x]=2;
	for(auto v:adj[x]){
		check(v);
	}
	col[x]=1;
}
	
void pre(int x){
	sz[x]=1;
	for(auto v:adj[x]){
		pre(v);
		sz[x]+=sz[v];
	}
}
int qexp(int a, int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}
int inv(int x){
	return qexp(x,mod-2);
}
int dfs(int x){
	int N = sz[x];
	int res = 1;
	for(auto v:adj[x]){
		res=(res*dfs(v))%mod;
	}
	int ways=F[N-1];
	for(auto v:adj[x]){
		ways=(ways*inv(F[sz[v]]))%mod;
	}
	return res*ways%mod;
}
int32_t main(){
	F[0]=1;
	for(int i=1;i<maxn;i++){
		F[i]=F[i-1]*i%mod;
	}
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		in[b]++;
		tadj[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		if(in[i] == 0){
			tadj[0].push_back(i);
			in[i]++;
		}
	}
	queue<int>qu;
	qu.push(0);
	while(qu.size()){
		int cur=qu.front();qu.pop();
		for(auto v:tadj[cur]){
			in[v]--;
			if(in[v]==0){
				adj[cur].push_back(v);
				qu.push(v);
			}
		}
	}
	int rt=0;
	pre(rt);
	cout<<dfs(rt)*inv(F[n])%mod;
}