#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,x,cnt,hea[N],dfn[N],pre[N],tim,sta[N],nsta,nnp,belo[N],quan[N],cnt2,wei[N],rd[N];
int a,b,f[N],ans[N],maxans,maxnum,top;
bool vis[N];
map<int,map<int,bool> > mymap;
queue<int> myq;
struct qwe{
	int star,net,to;
}bi[M],ci[M];
void add(int now,int to){
	bi[++cnt].to=to;
	bi[cnt].star=now;
	bi[cnt].net=hea[now];
	hea[now]=cnt;
}
void add2(int now,int to){
	ci[++cnt2].to=to;
	ci[cnt2].star=now;
	ci[cnt2].net=wei[now];
	wei[now]=cnt2;
}
void tarj(int now){
	dfn[now]=pre[now]=++tim;
	vis[now]=1;
	sta[++top]=now;
	for(int i=hea[now];i;i=bi[i].net){
		int to=bi[i].to;
		if(!dfn[to]){
			tarj(to);
			pre[now]=min(pre[now],pre[to]);
		}
		else if(vis[to]) pre[now]=min(pre[now],pre[to]);
	}
	if(pre[now]==dfn[now]){
		++nnp;int dd=0;
		while(sta[top]!=now){
			belo[sta[top]]=nnp;vis[sta[top]]=0;top--;dd++;
		}
		belo[sta[top]]=nnp;vis[sta[top]]=0;top--;dd++;
		quan[nnp]=dd;
	}
}
void cj(){
	for(int i=1;i<=m;i++){
		if(!mymap[belo[bi[i].star]][belo[bi[i].to]]&&(belo[bi[i].star]!=belo[bi[i].to])){
			add2(belo[bi[i].star],belo[bi[i].to]);
			mymap[belo[bi[i].star]][belo[bi[i].to]]=1;
			rd[belo[bi[i].to]]++;
		}
	}
	int startt;
	for(int i=1;i<=nnp;i++) f[i]=quan[i],ans[i]=1;
	for(int k=1;k<=nnp;k++) if(!rd[k]) myq.push(k);
	while(!myq.empty()){	
		int now=myq.front();
		myq.pop();
		bool bb=0;
		if(wei[now]) bb=1;
		for(int i=wei[now];i;i=ci[i].net){
			int to=ci[i].to;
			rd[to]--;
			if(!rd[to]) myq.push(to);
			if(f[to]<f[now]+quan[to]){
				f[to]=f[now]+quan[to];ans[to]=ans[now];
				if(ans[to]>=x) ans[to]%=x;
			}
			else if(f[to]==f[now]+quan[to]){
				ans[to]=ans[now]+ans[to];
				if(ans[to]>=x) ans[to]%=x;
			} 
		}
		if(bb)f[now]=0,ans[now]=0;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i]) tarj(i);
	cj();
	for(int i=1;i<=nnp;i++){
		if(maxans<f[i]) maxans=f[i],maxnum=ans[i];
		else if(maxans==f[i]) maxnum+=ans[i],maxans%=x;
	}
	printf("%d\n%d",maxans,maxnum);
	return 0;
}