#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);
	}
}
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);
	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			if (used[to] != used[i]) g1[used[i]].push_back(used[to]);
		}
	}
	vector<int> tp = used;
	if (fl) {
		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;
			for (auto el : edg) {
				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) continue;
				vector<int> cnt1(t1, 0);
				for (int i = 0; i < ver[col]; i++) cnt1[used[i]]++;
				if (cnt1[used[el.first]] == 1 && cnt1[used[el.second]] == 1) cnt++;
			}
			if (cnt == 0) continue;
			if (cnt == 1) mx++;
			if (cnt >= 2) {
				mx += 2; ll w = cnt * 1ll * (cnt - 1) / 2ll;
				w %= mod; cnt0 = (cnt0 * 1ll * w) % mod;
			}
		}
		cout << mx << "\n" << cnt0; exit(0);
	}
	//for (int i = 0; i < n; i++) cout << tp[i] << " ";
	//cout << endl;
	//for (int i = 1; i < t; i++) cout << ver[i] << " " << ed[i] << "     ";
	//cout << endl;
	int mx = 0, cnt0 = 1;
	for (int i = 1; i < t; i++) {
		if (ver[i] >= 3) {
			int ln = ver[i] * (ver[i] - 1) / 2;
			mx += 2, cnt0 = (cnt0 * 1ll * ln) % mod;
		}
	}
	int ln = t - 1; int edg = 0, edg0 = 0;
	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			//cout << i << " " << to << " " << tp[i] << " " << tp[to] << " " << ver[tp[i]] << " " << ver[tp[to]] << " edge\n";
			if (ver[tp[i]] == 1 && ver[tp[to]] == 1 && tp[i] != tp[to]) edg++;
		}
	}
	for (int i = 1; i < t; i++) edg0 += g1[i].size();
	//cout << edg0 << " " << edg << " " << ln << endl;
	if (ln * (ln - 1) / 2 != edg0) {
		cout << mx << endl << cnt0; exit(0);
	}
	mx++; cnt0 = (cnt0 * 1ll * edg) % mod; cout << mx << "\n" << cnt0;
	return 0;
}
