#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 };
}

vector<ll> depth;
vector<vector<ll>> graph2;
vector<ll> color;
ll dfs(ll i, vector<vector<ll>>& graph) {
	color[i] = 1;
	ll upto = depth[i];
	for (auto p : graph[i]) {
		if (color[p] == 2) continue;
		if (color[p] == 1) {
			upto = min(upto, depth[p]);
			continue;
		}
		depth[p] = depth[i] + 1;
		ll u = dfs(p, graph);
		if (u <= depth[i]) {
			graph2[i].push_back(p);
			graph2[p].push_back(i);
		}
		upto = min(upto, u);
	}
	color[i] = 1;
	return upto;
}

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

void dfs(ll i, ll c) {
	color[i] = c;
	for (auto p : graph2[i]) {
		if (color[p] != -1) continue;
		dfs(p, c);
	}
}

vector<ll> topsort;
void tdfs(int i, vector<vector<ll>>& graph, vector<bool>& used) {
	used[i] = true;
	for (auto p : graph[i]) {
		if (used[p]) continue;
		tdfs(p, graph, used);
	}
	topsort.push_back(i);
}

void paint(int i, vector<vector<ll>>& graph, vector<ll>& color, ll c) {
	color[i] = c;
	for (auto p : graph[i]) {
		if (color[p] == -1) paint(p, graph, color, c);
	}
}

vector<ll> divide_kss(vector<vector<ll>> graph) {
	ll n = graph.size();
	vector<ll> ans(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 = ans[j];
				break;
			}
		}
		if (cur == c) c++;
		ans[i] = cur;
	}

	return ans;
}

/*
pair<ll, ll> solve_stupid(vector<vector<ll>> graph) {
	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 });
		}
	}
	ll m = edges.size();
	vector<ll> d = divide_kss(graph);
	vector<ll> masks;
	for (ll i = 0; i < (1ll << m); i++) {
		vector<vector<ll>> ng;
		int msk = i;
		for (int j = 0; j < m; j++) {
			ll k = msk % 2;
			msk /= 2;
			if (k == 0) {
				ng[edges[j].first].push_back(edges[j].second);
			}
			else {
				ng[edges[j].second].push_back(edges[j].first);
			}
		}
		auto cd = divide_kss(ng);
		if (cd == d) masks.push_back(i);
	}
}
*/

mt19937 rnd(2);

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

	while (true) {
		ll n = 100, m = 200, g = 0; cin >> n >> m >> g;
	//n = 140, m = 140;
		vector<vector<ll>> graph(n);
		vector<pair<ll, ll>> edges;
		while (m--) {
			ll a, b; cin >> a >> b; a--; b--;
			
			//a = rnd() % n;
			//b = rnd() % n;
			//if (a > b) swap(a, b);
			//if (a == b) continue;
			
			graph[a].push_back(b);
			edges.push_back({ a, b });
		}
		auto answ = solve_DAG(graph);
		//cout << answ.first << " " << answ.second << endl;
		//return 0;
		//return 0;
		
		auto ans = solve_DAG(graph);
		cout << ans.first << " " << ans.second << endl;
		return 0;
		vector<ll> cs(c);
		vector<ll> ingraph;
		for (auto p : dividing) {
			ingraph.push_back(cs[p]);
			cs[p]++;
		}
		vector<vector<vector<ll>>> graphs;
		for (auto p : cs) graphs.push_back(vector<vector<ll>>(p));
		for (auto p : edges) {
			ll c1 = dividing[p.first], c2 = dividing[p.second];
			if (c1 != c2) continue;
			ll a = ingraph[p.first], b = ingraph[p.second];
			graphs[c1][a].push_back(b);
		}
		for (auto g : graphs) {
			auto lans = solve_component(g);
			ans.first += lans.first;
			ans.second = (ans.second * lans.second) % MOD;
		}
		
		/*if (ans.first != answ.first) {
			cout << "WA";
			cin >> n;
		}
		else {
			cout << "OK" << endl;
		}*/
		//for (auto p : dividing) cout << p << " "; cout << endl;
		cout << ans.first << " " << ans.second << endl;
		return 0;
	}
}