#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <ctime>
#include <chrono>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <bitset>
#include <queue>
using namespace std;
mt19937_64 rnd(time(NULL));

const long long INF = 1e18, MOD = 1e9 + 7;

bool bit(long long m, long long i)
{
	return ((m >> i) & 1);
}

long long G;

void dfs_top(long long v, vector<vector<long long>>& g, vector<bool>& used, vector<long long>& top)
{
	used[v] = true;
	for (auto& i : g[v])
	{
		if (used[i])
		{
			continue;
		}

		dfs_top(i, g, used, top);
	}
	top.push_back(v);
}

void dfs_comp(long long v, vector<vector<long long>>& rg, vector<long long>& comp, long long comps)
{
	comp[v] = comps;
	for (auto& i : rg[v])
	{
		if (comp[i] != -1)
		{
			continue;
		}

		dfs_comp(i, rg, comp, comps);
	}
}

vector<long long> calc_comps(vector<vector<long long>>& g)
{
	long long n = g.size();
	vector<vector<long long>> rg(n);
	for (long long i = 0; i < n; i++)
	{
		for (auto& j : g[i])
		{
			rg[j].push_back(i);
		}
	}

	vector<bool> used(n);
	vector<long long> top, comp(n, -1);
	long long comps = 0;
	for (long long i = 0; i < n; i++)
	{
		if (used[i])
		{
			continue;
		}

		dfs_top(i, g, used, top);
	}
	reverse(top.begin(), top.end());
	comp.resize(n, -1);
	for (auto& i : top)
	{
		if (comp[i] != -1)
		{
			continue;
		}

		dfs_comp(i, rg, comp, comps);
		comps++;
	}

	vector<long long> rename(comps + 1, -1);
	long long nxt_name = 0;
	for (auto& i : comp)
	{
		if (rename[i] == -1)
		{
			rename[i] = nxt_name++;
		}
		i = rename[i];
	}
		
	return comp;
}

void solve()
{
	long long n, m;
	cin >> n >> m >> G;
	vector<pair<long long, long long>> e;
	vector<vector<long long>> g(n);
	for (long long i = 0; i < m; i++)
	{
		long long a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		e.push_back({ a, b });
	}

	vector<long long> init = calc_comps(g);
	long long best_size = -1, ans = 0;
	for (long long mask = 0; mask < (1ll << m); mask++)
	{
		for (long long i = 0; i < n; i++)
		{
			g[i].clear();
		}
		vector<pair<long long, long long>> oth;
		for (long long i = 0; i < m; i++)
		{
			if (bit(mask, i))
			{
				g[e[i].first].push_back(e[i].second);
			}
			else
			{
				oth.push_back(e[i]);
			}
		}
		long long cnto = oth.size();
		if (cnto < best_size)
		{
			continue;
		}
		bool huy = false;
		for (long long msk = 0; msk < (1ll << cnto) - 1; msk++)
		{
			for (long long i = 0; i < cnto; i++)
			{
				if (bit(msk, i))
				{
					g[oth[i].first].push_back(oth[i].second);
				}
				else
				{
					g[oth[i].second].push_back(oth[i].first);
				}
			}
			vector<long long> res = calc_comps(g);
			if (res == init)
			{
				huy = true;
				break;
			}
			for (long long i = 0; i < cnto; i++)
			{
				if (bit(msk, i))
				{
					g[oth[i].first].pop_back();
				}
				else
				{
					g[oth[i].second].pop_back();
				}
			}
		}
		if (huy)
		{
			continue;
		}

		if (cnto > best_size)
		{
			best_size = cnto;
			ans = 0;
		}
		if (cnto == best_size)
		{
			ans++;
		}
	}
	cout << best_size << "\n" << ans % MOD << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}

/*

























*/
