#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <iomanip>
using namespace std;
using ll = long long;
using ld = long double;
#define endl '\n'
const int mod = 1e9 + 7;
vector<int> ord; vector<int> used;
void dfs1(int v, vector<vector<int>>& g, pair<int, int> edg) {
	used[v] = 1;
	for (auto to : g[v]) {
		if (v == edg.first && to == edg.second) continue;
		if (!used[to]) dfs1(to, g, edg);
	}
	ord.push_back(v);
}
void dfs2(int v, int col, vector<vector<int>>& tg, pair<int, int> edg) {
	used[v] = col;
	for (auto to : tg[v]) {
		if (v == edg.second && to == edg.first) continue;
		if (!used[to]) dfs2(to, col, tg, edg);
	}
}
bool cycle(int v, int pr, vector<vector<int>>& g) {
	used[v] = 1;
	for (auto to : g[v]) {
		if (!used[to]) {
			bool byl = cycle(to, v, g);
			if (byl) return 1;
			continue;
		}
		if (to != pr) return 1;
	}
	return 0;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	vector<vector<int>> g, tg, g1;
	int n, m, groop; cin >> n >> m >> groop; g.resize(n); tg.resize(n);
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); tg[v].push_back(u);
	}
	used.resize(n, 0);
	for (int i = 0; i < n; i++) {
		if (!used[i]) dfs1(i, g, { -1, -1 });
	}
	used.assign(n, 0); int t = 1; reverse(ord.begin(), ord.end());
	for (int i = 0; i < n; i++) {
		if (!used[ord[i]]) dfs2(ord[i], t++, tg, { -1, -1 });
	}
	vector<int> ver(t), ed(t);
	for (int i = 0; i < n; i++) {
		ver[used[i]]++;
		for (auto to : g[i]) {
			if (used[to] == used[i]) ed[used[i]]++;
		}
	}
	bool fl = 0;
	for (int i = 1; i < t; i++) {
		int em = ver[i] * (ver[i] - 1) / 2;
		if (ed[i] != em) fl = 1;
	}
	g1.resize(t); vector<vector<int>> tg1(t);
	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			if (used[to] != used[i]) g1[used[i]].push_back(used[to]), tg1[used[to]].push_back(used[i]);
		}
	}
	vector<int> tp = used;
	int mx = 0, cnt0 = 1;
	for (int col = 1; col < t; col++) {
		if (ver[col] <= 2) continue;
		vector<vector<int>> gg(ver[col]), tgg(ver[col]);
		vector<int> vr;
		for (int i = 0; i < n; i++) {
			if (tp[i] == col) vr.push_back(i);
		}
		vector<pair<int, int>> edg;
		for (int i = 0; i < n; i++) {
			if (tp[i] != col) continue;
			int nm = lower_bound(vr.begin(), vr.end(), i) - vr.begin();
			for (auto to : g[i]) {
				if (tp[to] != col) continue;
				int nm1 = lower_bound(vr.begin(), vr.end(), to) - vr.begin();
				gg[nm].push_back(nm1); tgg[nm1].push_back(nm); edg.push_back({ nm, nm1 });
			}
		}
		int cnt = 0; vector<pair<int, int>> edg1;
		for (auto el : edg) {
			int p = 0, p1 = 0;; int u = el.first, v = el.second;
			for (; p < gg[u].size() && gg[u][p] != v; p++);
			gg[u].erase(gg[u].begin() + p); gg[v].push_back(u);
			for (; p1 < tgg[v].size() && tgg[v][p1] != u; p1++);
			tgg[v].erase(tgg[v].begin() + p1); tgg[u].push_back(v);
			used.assign(ver[col], 0); ord.clear();
			for (int i = 0; i < ver[col]; i++) {
				if (!used[i]) dfs1(i, gg, el);
			}
			reverse(ord.begin(), ord.end()); int t1 = 1; used.assign(ver[col], 0);
			for (int i = 0; i < ver[col]; i++) {
				if (!used[ord[i]]) dfs2(ord[i], t1++, tgg, el);
			}
			if (t1 != 2) {
				edg1.push_back({ u, v });
			}
			gg[v].pop_back(); gg[u].insert(gg[u].begin() + p, v); tgg[u].pop_back(); tgg[v].insert(tgg[v].begin() + p1, u);
		}
		for (auto el : edg1) {
			if ((el.first + 1) % ver[col] == el.second) cnt++;
		}
		if (cnt != edg1.size()) exit(-1);
		if (cnt < ver[col]) {
			mx += cnt; continue;
		}
		mx += ver[col] - 1; cnt0 = (cnt0 * 1ll * ver[col]) % mod;
	}
	int cnt2 = 0; n = t;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < g1[i].size(); j++) {
			int u = i, v = g1[i][j]; g1[i].erase(g1[i].begin() + j); g1[v].push_back(u);
			tg1[i].push_back(v);
			int ps = 0;
			for (; ps < tg1[v].size() && tg1[v][ps] != u; ps++);
			tg1[v].erase(tg1[v].begin() + ps);
			used.assign(n, 0); ord.clear();
			for (int p = 1; p < n; p++) {
				if (!used[p]) dfs1(p, g1, { -1, -1 });
			}
			reverse(ord.begin(), ord.end()); used.assign(n, 0); t = 1;
			for (int p = 0; p < n - 1; p++) {
				//cout << p << " start " << tg1.size() << endl;
				if (!used[ord[p]]) dfs2(ord[p], t++, tg1, { -1, -1 });
			}
			if (t != n) cnt2++;
			g1[i].insert(g1[i].begin() + j, v); g1[v].pop_back(); tg1[i].pop_back(); tg1[v].insert(tg1[v].begin() + ps, i);
		}
	}
	mx += cnt2;
	cout << mx << "\n" << cnt0;
	return 0;
}
