#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); } struct node{ bitset<210>A[210]; node(){ for(int i=0;i<210;i++) A[i].reset(); } friend node operator *(const node A,const node B){ node C; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(A.A[i][j]) C.A[i]|=B.A[j]; return C; } friend bool operator ==(const node A,const node B){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(A.A[i][j]!=B.A[i][j])return 0; return 1; } }G,BS; inline node QP(node A,int x){ x--; node res=A; while(x){ if(x&1)res=res*A; A=A*A; x>>=1; } return res; } inline bool chk(int k){ return QP(G,k)==QP(G,k)*BS; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("ex_lost3.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); if(t) G.A[u][v]=1; } 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]){ 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; if(t){ BS=G; for(int i=1;i<=n;i++) BS=QP(BS,qp(i,mx[i])); int l=1,r=n*n*n; while(l<r){ int mid=l+r>>1; if(chk(mid))r=mid; else l=mid+1; } cout<<l<<" "; } cout<<res<<endl; cout.flush(); return 0; }