#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;

long long n;
vector<long long> g[2000], rg[2000];
vector<long long> comp;
long long comps = 0;

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

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

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

		dfs_comp(i);
	}
}

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

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

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

		dfs_comp(i);
		comps++;
	}

	vector<long long> in(n);
	for (auto& i : e)
	{
		in[i.second]++;
	}
	long long del = 0, ans = 1;
	for (long long i = 0; i < n; i++)
	{
		if (!in[i])
		{
			continue;
		}

		ans *= (in[i] - 1);
		ans %= MOD;
		del += in[i] - 1;
	}
	cout << del << " " << ans << "\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;
}

/*

























*/
