#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1'000'000'007;

template<typename T>
bool assign_max(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

bool dfs(ll v, vector<bool>& used, vector<set<ll>>& arr, ll need) {
	if (v == need) {
		return true;
	}
	used[v] = true;
	for (auto i : arr[v]) {
		if (!used[i]) {
			if (dfs(i, used, arr, need)) {
				return true;
			}
		}
	}
	return false;
}

void dfs2(ll v, vector<ll>& c, vector<vector<ll>>& sc) {
	for (auto i : sc[v]) {
		if (c[i] == -1) {
			c[i] = c[v];
			dfs2(i, c, sc);
		}
	}
}

void clear(vector<bool>& used, vector<ll> ntc = vector<ll>(0, 0)) {
	if (ntc.empty()) {
		for (ll i = 0; i < used.size(); i++) {
			used[i] = false;
		}
	} else {
		for (auto i : ntc) {
			used[i] = false;
		}
	}
}

pair<ll, ll> calc(vector<ll> vs, vector<bool>& used, vector<set<ll>>& to) {
	vector<pair<ll, ll>> rs;
	for (auto i : vs) {
		for (auto j : to[i]) {
			rs.emplace_back(i, j);
		}
	}
	ll a1 = 0, a2 = 1;
	for (ll i = 1; i < (1 << rs.size()); i++) {
		bool bb = true;
		ll nc = 0;
		vector<pair<ll, ll>> add;
		for (ll j = 0; j < rs.size(); j++) {
			if ((i >> j) & 1) {
				nc++;
				auto[a, b] = rs[j];
				to[a].erase(b);
				if (dfs(a, used, to, b)) {
					clear(used, vs);
					to[a].insert(b);
					bb = false;
					break;
				}
				clear(used, vs);
				to[a].insert(b);
				to[b].insert(a);
				add.emplace_back(a, b);
			}
		}
		for (auto[a, b] : add) {
			to[b].erase(a);
		}
		if (bb) {
			if (assign_max(a1, nc)) {
				a2 = 0;
			}
			if (a1 == nc) {
				a2++;
			}
		}
	}
	/*
	for (auto[a, b] : rs) {
		to[a].erase(b);
		if (!dfs(a, used, to, b)) {
			a1++;
			to[b].insert(a);
		}
		clear(used, vs);
		to[a].insert(b);
	}
	*/
	return make_pair(a1, a2);
}

void solve() {
	ll n, m, g;
	cin >> n >> m >> g;
	vector<set<ll>> to(n);
	vector<pair<ll, ll>> all;
	for (ll i = 0; i < m; i++) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		all.emplace_back(a, b);
		to[a].insert(b);
	}
	vector<vector<ll>> sc(n);
	vector<bool> used(n, false);
	for (auto[a, b] : all) {
		if (dfs(b, used, to, a)) {
			sc[a].push_back(b);
			sc[b].push_back(a);
		}
		clear(used);
	}
	vector<ll> c(n, -1);
	ll lst = 0;
	for (ll i = 0; i < n; i++) {
		if (c[i] == -1) {
			c[i] = lst;
			dfs2(i, c, sc);
			lst++;
		}
	}
	vector<vector<ll>> allc(lst);
	for (ll i = 0; i < n; i++) {
		allc[c[i]].push_back(i);
	}
	vector<set<ll>> nto(n);
	for (auto[a, b] : all) {
		if (c[a] == c[b]) {
			nto[a].insert(b);
		}
	}
	ll ans = 0;
	ll cv = 1;
	for (ll i = 0; i < lst; i++) {
		auto[a, b] = calc(allc[i], used, nto);
		ans += a;
		cv = (cv * b) % MOD;
	}
	for (auto[a, b] : all) {
		if (c[a] == c[b]) {
			continue;
		}
		to[a].erase(b);
		if (dfs(a, used, to, b)) {
			ans++;
		}
		clear(used);
		to[a].insert(b);
	}
	cout << ans << '\n' << cv << '\n';
}

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