#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<random>
#include<chrono>
#include<set>
#include<map>
#include<deque>
#include<array>
//#define int long long
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
using namespace std;
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());
int mod = 1e9 + 7;
vector<int> par, siz;
int find(int i) {
	return par[i] = (par[i] == i ? i : find(par[i]));
}
void union_sets(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	if (siz[a] < siz[b])swap(a, b);
	par[b] = a;
	siz[a] += siz[b];
}
vector<vector<int>> g, rg;
void solve() {
	int n, m, G;
	cin >> n >> m >> G;
	g.resize(n);
	rg.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		rg[b].push_back(a);
	}
	par.resize(n);
	siz.resize(n);
	for (int i = 0; i < n; i++) {
		par[i] = i;
		siz[i] = 1;
	}
	int ans = 0;
	ll ans2 = 1;
	for (int i = 0; i < n; i++) {
		map<int, int> mp;
		for (auto to : rg[i]) {
			mp[find(to)]++;
		}
		for (auto p : mp) {
			ans += p.second - 1;
			ans2 = (ans2 * p.second) % mod;
		}
		for (auto to : rg[i]) {
			union_sets(to, i);
		}
	}
	cout << ans << " " << ans2;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
}
