#include <bits/stdc++.h> using namespace std; #define int long long int n,m; const int M=1e9+7; int dep[200300]; bool vis[200300],ins[200300]; int low[200300],dfn[200300],d[200300]; vector<int>g[200300],gg[200300]; int w[200300],bel[200300],tk,cnt; int loc[200300]; stack<int>S; int fa[200300]; inline void dfs(int u){ loc[low[u]=dfn[u]=++tk]=u; S.push(u); for(int v:g[u]) if(!dfn[v]){ fa[v]=u; dfs(v); gg[u].push_back(v); if(low[v]<low[u]) d[u]=d[v]+1,low[u]=low[v]; } else if(!bel[v]){ if(dfn[v]<low[u]) d[u]=1,low[u]=dfn[v]; } if(dfn[u]==low[u]){ cnt++; while(!S.empty()){ int x=S.top(); S.pop(); bel[x]=cnt; if(x==u)break; } } } int mx[200300]; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline void dfsd(int u){ for(int v:gg[u])if(bel[v]==bel[u]){ dep[v]=dep[u]+1; dfsd(v); } } inline int gcd(int x,int y){ if(y==0)return x; else return gcd(y,x%y); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("lost.in","r",stdin); // freopen("lost.out","w",stdout); int t; cin>>n>>m>>t; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); } for(int i=1;i<=n;i++) if(!bel[i])dfs(i); for(int i=1;i<=n;i++){ int u=loc[i]; if(low[u]==dfn[u]) dfsd(u); // cout<<u<<" "<<d[u]<<" "<<dep[u]<<endl; for(int v:g[u]) if(bel[v]==bel[u]&&dfn[v]<dfn[u]){ // cout<<u<<" "<<v<<" "<<dep[u]<<" "<<d[v]<<" "<<dfn[u]<<" "<<dfn[v]<<endl; // cerr<<w[bel[u]]<<" "<<dep[u]+d[v]+1<<endl; w[bel[u]]=gcd(w[bel[u]],dep[u]+d[v]+1);} } // for(int i=1;i<=cnt;i++) // cerr<<w[i]<<" "; // cerr<<endl; // return 0; for(int i=1;i<=cnt;i++){ int x=w[i]; if(!x)continue; // cerr<<x<<" "<<endl; for(int j=2;j*j<=x;j++) if(x%j==0){ int c=0; while(x%j==0)x/=j,c++; mx[j]=max(mx[j],c); } if(x!=1)mx[x]=max(mx[x],1ll); } int res=1; for(int i=1;i<=n;i++) res=res*qp(i,mx[i])%M; cout<<res<<endl; cout.flush(); return 0; }