#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <array>
#include <queue>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) a.begin(), a.end()
const ll N = 2001, MOD = 1e9 + 7;
ll n, m, group;
void calcDAGdfs(ll u, ll nch, vector<vector<ll>>& g, vector<vector<char>>& p, vector<ll>& us) {
	p[nch][u] = 1;
	us[u] = nch;
	for (ll v : g[u]) {
		if (us[v] < nch) {
			calcDAGdfs(v, nch, g, p, us);
		}
	}
}
ll calcDAG(vector<vector<ll>>& g) {
	ll n = g.size();
	vector<vector<char>> p(n, vector<char>(n, 0));
	vector<ll> us(n, -1);
	for (ll u = 0; u < n; u++) {
		calcDAGdfs(u, u, g, p, us);
		p[u][u] = 0;
	}
	ll res = 0;
	for (ll u = 0; u < n; u++) {
		for (ll v : g[u]) {
			char is = 1;
			for (ll k = 0; k < n; k++) {
				is &= !(p[u][k] && p[k][v]);
			}
			res += is;
		}
	}
	return res;
}
ll binpow(ll a, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n % 1) ans = (ans * a) % MOD;
		a = (a * a) % MOD;
		n /= 2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> group;
	vector<vector<ll>> g(n);
	vector<ll> rb(2 * n, 0);
	for (ll i = 0; i < m; i++) {
		ll u, v;
		cin >> u >> v;
		u--; v--;
		g[u].push_back(v);
		if ((u + 1) % n != v) {
			if (u < v) {
				rb[v] = max(rb[v], u + 1);
				rb[n + v] = max(rb[n + v], n + u + 1);
			}
			else {
				rb[n + v] = max(rb[n + v], u + 1);
			}
		}
	}
	vector<ll> res(2 * n), cnt(2 * n);
	map<ll, ll> sup;
	for (ll i = 0; i < n; i++) {
		res[i] = 1, cnt[i] = 1;
		ll l = i;
		map<ll, ll> glob; glob[res[i]] = cnt[i];
		for (ll j = i + 1; j <= i + n; j++) {
			res[j] = glob.begin()->first + 1;
			cnt[j] = glob.begin()->second % MOD;
			glob[res[j]] += cnt[j];
			ll nl = max(l, rb[j]);
			for (; l < nl; l++) {
				glob[res[l]] -= cnt[l];
				if (glob[res[l]] == 0) glob.erase(res[l]);
			}
		}
		sup[res[i + n] - 1] += cnt[i + n];
	}
	cout << n - sup.begin()->first << "\n"
		<< sup.begin()->second % MOD * binpow(sup.begin()->first, MOD - 2) % MOD<< "\n";
	return 0;
}