#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10,mod=1e9+7; int n,m,t,vis[maxn],dis[maxn],res[maxn],tag[maxn],bel[maxn],G; int stk[maxn],tp,instk[maxn],dfn[maxn],low[maxn],ct,cc; vector<int>v[maxn],D[maxn]; int gcd(int a,int b){return ((!b)?a:gcd(b,a%b));} void tar(int u){ dfn[u]=low[u]=++ct; stk[++tp]=u,instk[u]=1; for(int x:v[u]){ if(!dfn[x])tar(x),low[u]=min(low[u],low[x]); else if(instk[x])low[u]=min(low[u],dfn[x]); }if(dfn[u]==low[u]){++cc; while(tp){ int x=stk[tp--]; instk[x]=0,bel[x]=cc; if(x==u)break; } } } void dfs(int u){ vis[u]=1; for(int x:v[u])if(bel[x]==bel[u]){ if(!vis[x]){dis[x]=dis[u]+1;dfs(x);} else G=gcd(G,abs(dis[u]+1-dis[x])); } } int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod,b>>=1; }return res; } struct mat { int n,m; bitset<205>B[205]; void init(int _n,int _m){ n=_n,m=_m; up(i,1,n)B[i].reset(); } }A; mat operator*(mat a,mat b){ mat c;c.init(a.n,b.m); up(i,1,a.n)up(j,1,a.m)if(a.B[i][j])c.B[i]|=b.B[j]; return c; } bool operator==(mat a,mat b){ up(i,1,a.n)if((a.B[i]^b.B[i]).any())return 0; return 1; } mat qpow(mat a,int b){ mat res=a;b--; while(b){ if(b&1)res=res*a; a=a*a,b>>=1; }return res; } mat gp(mat a){ up(i,1,n)if(res[i])a=qpow(a,qpow(i,res[i])); return a; } void calc(){ A.init(n,n); up(i,1,n)for(int x:v[i])A.B[i][x]=1; int l=0,r=5e4; mat f=gp(A); while(l+1<r){ int mid=l+r>>1; mat f1=qpow(A,mid),f2=f1*f; if(f1==f2)r=mid; else l=mid; }printf("%d ",r); } void slv(){ n=read(),m=read(),t=read(); up(i,1,m){ int x=read(),y=read(); v[x].p_b(y); }up(i,2,n)if(D[i].empty())for(int j=i;j<=n;j+=i)D[j].p_b(i); up(i,1,n)if(!dfn[i])tar(i); up(i,1,n)if(!vis[i])G=0,dfs(i),tag[G]=1; up(i,1,n)if(tag[i]){ int w=i; for(int x:D[i]){ int c=0;while(!(w%x))w/=x,c++; res[x]=max(res[x],c); } } int ret=1; up(i,1,n)ret=ret*1ll*qpow(i,res[i])%mod; if(t==1)calc(); printf("%d\n",ret); }int main(){ //freopen("lost.in","r",stdin); //freopen("lost.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }