#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll n, m, G;
vector<vector<ll>> g, rg;
vector<ll> p, u, c;
void dfs(ll v) {
	u[v] = 1;
	for (auto to : g[v]) {
		if (!u[to]) dfs(to);
	}
	p.push_back(v);
}
void dfs1(ll v, ll col) {
	c[v] = col;
	for (auto to : rg[v]) {
		if (c[to] == -1) dfs1(to, col);
	}
}
void cmp() {
	u.assign(n, 0);
	p = {};
	for (ll i = 0; i < n; ++i) {
		if (!u[i]) dfs(i);
	}
	ll cl = 0;
	c.assign(n, -1);
	reverse(p.begin(), p.end());
	for (ll i = 0; i < (ll)p.size(); ++i) {
		if (c[p[i]] == -1) dfs1(p[i], p[i]);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> G;
	g.resize(n);
	rg.resize(n);
	vector<pair<ll, ll>> e;
	for (ll i = 0; i < m; ++i) {
		ll u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		rg[v].push_back(u);
		e.push_back({ u, v });
	}
	vector < vector<ll>> g0 = g, rg0 = rg;
	vector<pair<ll, ll>> e0 = e;
	ll ans1 = 0, ans2 = 0, mod = 1e9 + 7;
	vector<ll> z((1 << m), 0);
	cmp();
	vector<ll> c0 = c;
	for (ll i = 0; i < (1 << m); ++i) {
		g.assign(n, {});
		rg.assign(n, {});
		for (ll j = 0; j < m; ++j) {
			if ((i & (1 << j)) == 0) g[e[j].first].push_back(e[j].second), rg[e[j].second].push_back(e[j].first);
			else g[e[j].second].push_back(e[j].first), rg[e[j].first].push_back(e[j].second);
		}
		cmp();
		if (c == c0) z[i] = 1;
	}
	for (ll i = 0; i < (1 << m); ++i) {
		ll b = 0;
		for (ll j = i; ; j = ((j - 1) & i)) {
			b += z[j];
			if (b > 1) break;
			if (j == 0) break;
		}
		if (b == 1) {
			ll cnt = 0;
			for (ll j = 0; j < m; ++j) {
				if (i & (1 << j)) ++cnt;
			}
			if (cnt > ans1) ans1 = cnt, ans2 = 0;
			if (cnt == ans1) ans2 = (ans2 + 1) % mod;
		}
	}
	cout << ans1 << "\n" << ans2;
	cout << endl;
	return 0;
}