#include <iostream>
#include <vector>
using namespace std;

#define int long long
const int MOD = 1e9 + 7;

struct DSU {
	vector <int> p;
	vector <int> sz;
	int n;

	DSU(int n) {
		this->n = n;
		p.resize(n);
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		sz.resize(n, 1);
	}

	int get(int x) {
		if (p[x] == x) return x;
		return p[x] = get(p[x]);
	}

	bool merge(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return 0;
		if (sz[x] > sz[y]) {
			swap(x, y);
		}
		p[x] = y;
		sz[y] += sz[x];
		return 1;
	}
};

vector <vector <int>> g;
vector <pair <int, int>> eds;

int T;
vector <int> used;

bool dfs(int v, int target, int a, int b) {
	if (v == target) return 1;
	if (used[v] == T) return 0;
	used[v] = T;
	for (auto u : g[v]) {
		if (v == a && u == b) continue;
		if (dfs(u, target, a, b)) return 1;
	}
	return 0;
}

bool check(int v, int u) {
	T++;
	return dfs(v, u, v, u);
}

signed main() {
	int n, m, G;
	cin >> n >> m >> G;
	g.resize(n);
	used.resize(n);
	T = 1;
	vector <vector <bool>> can(n, vector <bool>(n));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		eds.push_back({ a, b });
	}
	for (auto [a, b] : eds) {
		can[a][b] = check(a, b);
		can[b][a] = check(b, a);
	}

	DSU dsu(n);
	for (auto [a, b] : eds) {
		if (can[b][a]) {
			dsu.merge(a, b);
		}
	}
	vector <int> cnt_incomp(n);
	int cnt = 0;
	for (auto [a, b] : eds) {
		if (dsu.get(a) == dsu.get(b)) {
			cnt_incomp[dsu.get(a)] += !can[a][b];
		}
		else {
			if (can[a][b]) {
				cnt++;
			}
		}
	}/*
	for (int i = 0; i < n; i++) {
		cnt_incomp[dsu.get(i)]++;
	}*/
	int prod = 1;
	for (auto x : cnt_incomp) {
		if (x) {
			prod *= x;
			prod %= MOD;
			cnt += x - 1;
		}
	}
	cout << cnt << '\n' << prod;
}