玄关

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	ll val,cnt;
};
int n,m,X;
vector<int>v[100001],vv[100001],stck;
int dfn[100001],low[100001],scc[100001];
int Size[100001],in_stck[100001];
/////////////
void add(int a,int b){
	if(a!=b)vv[a].push_back(b);
}
int oii;
int tsc;
void tarjan(int x){
	low[x]=dfn[x]=++oii;
//	cout<<fixed<<setprecision(1);
	in_stck[x]=1,stck.push_back(x);
	for(auto i:v[x]){
		if(!dfn[i]){
			tarjan(i);
			low[x]=min(low[x],low[i]);
		}
		else if(in_stck[i]){
			low[x]=min(low[x],dfn[i]);
		}
	}
	if(low[x]==dfn[x]){
		++tsc;
		while(stck.back()!=x){
			scc[stck.back()]=tsc;
			Size[tsc]++;
			in_stck[stck.back()]=0;
			stck.pop_back();
		}
		Size[tsc]++;
		scc[x]=tsc;
		stck.pop_back();
		in_stck[x]=0;
	}
}
void topo(){
	ll mx=0,sm=0;
	node f[100001];
	ll in[100001]={},out[100001]={};
	queue<int>que;
	for(int i=1;i<=tsc;i++){
		for(int q:vv[i])in[q]++,out[i]++;
	}
	for(int i=1;i<=tsc;i++){
		if(in[i]==0){
			que.push(i);
			f[i].val=Size[i];
			f[i].cnt=1;
		}
	}
//	for(int i=1;i<=tsc;i++)cout<<in[i]<<" ";
//	cout<<"\n";
	while(!que.empty()){
		int tmp=que.front();que.pop();
		for(int i:vv[tmp]){
			int h=f[tmp].val+Size[i];
			if(h>f[i].val) f[i].val=h,f[i].cnt=f[tmp].cnt;
			else if(h==f[i].val) f[i].cnt+=f[tmp].cnt;
			f[i].cnt%=X;
			in[i]--;
			if(in[i]==0)que.push(i);
		}
	}
	for(int i=1;i<=tsc;i++){
//		cout<<f[i].val<<" "<<f[i].cnt<<"\n";
		if(out[i]==0){
			if(f[i].val>mx) mx=f[i].val,sm=f[i].cnt;
			else if(f[i].val==mx) sm+=f[i].cnt;
		}
	}
	cout<<mx<<"\n"<<sm%X;
}
int main(){
	// freopen("T1.in","r",stdin);
	// freopen("T1.out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	cin>>n>>m>>X;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
	}
	////////////tarjan 
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
//	for(int i=1;i<=tsc;i++){
//		cout<<Size[i]<<"\n";
//	}
	/////////////////
	
	
//	for(int i=1;i<=n;i++){
//		int h=0;
//		if((int)v[i].size())add(scc[i],scc[v[i][0]]);
//		for(int j=1;j<(int)v[i].size();j++){
//			if(scc[v[i][j-1]]!=scc[v[i][j]]){
//				add(scc[i],scc[j]);
//			}
//		}
//	}
	for(int i=1;i<=n;i++){
		for(int q:v[i]){
			add(scc[i],scc[q]);
		}
	}
	/////////////////////////////////////
	for(int i=1;i<=tsc;i++){
		sort(vv[i].begin(), vv[i].end());
		vv[i].erase(unique(vv[i].begin(), vv[i].end()), vv[i].end());
	}
	
//	for(int i=1;i<=tsc;i++){
//		cout<<i<<":";
//		for(int q:vv[i])cout<<q<<" ";
//		cout<<"\n";
//	}
	topo();
}