#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <unordered_set>
#include <random>
#include <map>
#include <numeric>

using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;

pair<ll, ll> solve_DAG(vector<vector<ll>> dag) {
	ll n = dag.size();
	ll cnt = 0;
	vector<pair<ll, ll>> edges;
	for (int i = 0; i < n; i++) {
		for (auto j : dag[i]) edges.push_back({ i, j });
	}
	for (auto e : edges) {
		vector<vector<ll>> dag2(n);
		for (int i = 0; i < n; i++) {
			for (auto p : dag[i]) {
				if (i == e.first && p == e.second) continue;
				dag2[p].push_back(i);
			}
		}
		vector<bool> can_get(n);
		can_get[e.first] = true;
		for (int i = e.first + 1; i <= e.second; i++) {
			for (auto p : dag2[i]) can_get[i] = can_get[i] || can_get[p];
		}
		if (can_get[e.second]) cnt++;
	}
	return { cnt, 1 };
}

void dfs(ll i, vector<vector<ll>>& graph, vector<bool>& used) {
	used[i] = true;
	for (auto p : graph[i]) {
		if (!used[p]) dfs(p, graph, used);
	}
}

pair<ll, ll> solve_component(vector<vector<ll>> graph) {
	ll cnt = 0;
	ll n = graph.size();
	vector<pair<ll, ll>> edges;
	for (int i = 0; i < graph.size(); i++) {
		for (auto j : graph[i]) {
			edges.push_back({ i, j });
		}
	}
	for (auto e : edges) {
		vector<vector<ll>> ngraph(n);
		for (int i = 0; i < n; i++) {
			for (auto j : graph[i]) {
				if (i == e.first && j == e.second) continue;
				ngraph[i].push_back(j);
			}
		}
		vector<bool> used(n, false);
		dfs(e.first, ngraph, used);
		if (used[e.second]) continue;
		used = vector<bool>(n, false);
		dfs(e.second, ngraph, used);
		if (!used[e.first]) continue;
		cnt++;
		graph[e.second].push_back(e.first);
	}
	return { cnt, 1 };
}

mt19937 rnd(2);

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n, m, g; cin >> n >> m >> g;
	vector<vector<ll>> graph(n);
	vector<pair<ll, ll>> edges;
	while (m--) {
		ll a, b; cin >> a >> b; a--; b--;
		graph[a].push_back(b);
		edges.push_back({ a, b });
	}
	auto answ = solve_DAG(graph);
	vector<ll> dividing(n);
	int c = 0;
	for (int i = 0; i < n; i++) {
		int cur = c;
		for (int j = 0; j < i; j++) {
			vector<bool> used;
			used.assign(n, false);
			dfs(i, graph, used);
			bool a = used[j];
			used.assign(n, false);
			dfs(j, graph, used);
			bool b = used[i];
			if (a && b) {
				cur = dividing[j];
				break;
			}
		}
		if (cur == c) c++;
		dividing[i] = cur;
	}
	vector<vector<ll>> dag(n);
	for (auto e : edges) {
		ll a = dividing[e.first], b = dividing[e.second];
		if (a == b) continue;
		dag[a].push_back(b);
	}
	auto ans = solve_DAG(dag);
	vector<ll> cs(c);
	vector<ll> ingraph;
	for (auto p : dividing) {
		ingraph.push_back(cs[p]);
		cs[p]++;
	}
	vector<vector<ll>> bgraph(n);
	for (auto p : edges) {
		ll c1 = dividing[p.first], c2 = dividing[p.second];
		if (c1 != c2) continue;
		bgraph[p.first].push_back(p.second);
	}
	auto lans = solve_component(bgraph);
	ans.first += lans.first;
	ans.second = (ans.second * lans.second) % MOD;
		
	cout << ans.first << " " << -1 << endl;
}