#include<bits/stdc++.h>

using namespace std;

const int N = 30;
vector<int> G[N], I[N], vec;
int n, m, g, u[N], v[N], scc[N];
bool seen[N];

void dfs(int x)
{
  if(seen[x]) return;
  seen[x] = 1;
  for(int y : G[x])
    dfs(y);
  vec.push_back(x);
}

void dfs2(int x, int r)
{
  if(!seen[x]) return;
  seen[x] = 0;
  scc[x] = r;
  for(int y : I[x])
    dfs2(y, r);
}


vector<int> Scclist()
{
  for(int i = 0; i < m; i ++)
    G[u[i]].push_back(v[i]), I[v[i]].push_back(u[i]);

  for(int i = 0; i < n; i ++)
    dfs(i);

  reverse(vec.begin(), vec.end());
  for(int i : vec)
    {
      if(!seen[i]) continue;
      dfs2(i, i);
    }
  vec.clear();

  cerr << "SCC :: ";
  for(int i = 0; i < m; i ++)
    cout << u[i] << ' ' << v[i] << endl;
  for(int i = 0; i < n; i ++)
    cout << scc[i] << ' ';
  cout << endl;
  
  int mi[n] = {};
  for(int i = 0; i < n; i ++) mi[i] = i;
  for(int i = 0; i < n; i ++)
    mi[scc[i]] = min(mi[scc[i]], i);

  vector<int> res(n);
  for(int i = 0; i < n; i ++)
    res[i] = mi[scc[i]], G[i].clear(), I[i].clear(), scc[i] = 0, seen[i] = 0;
  
  return res;
}

int main()
{
  cin >> n >> m >> g;

  for(int i = 0; i < m; i ++) {
    cin >> u[i] >> v[i];
    u[i]--, v[i]--;
  }
  vector<int> ori = Scclist();
  
  int ans = 0, w = 0;

  for(int mask = 0; mask < (1 << m); mask++)
    {
      if(__builtin_popcount(mask) < ans) continue;
      
      int ways = 0;
      for(int sub = mask; sub && !ways; sub = (sub - 1) & mask)
	{
	  for(int i = 0; i < m; i++)
	    if((1 << i) & sub)
	      swap(u[i], v[i]);
	  
	  vector<int> sol = Scclist();

	  if(sol == ori) ways++;
	  

	  for(int i = 0; i < m; i++)
	    if((1 << i) & sub) swap(u[i], v[i]);
	}

      if(ways == 0)
	{
	  int p = __builtin_popcount(mask);
	  if(ans < p)
	    ans = p, w = 1;
	  else if(ans == p)
	    w++;   
	}
	  
    }
  const int mod = (1e9 + 7);
  cout << ans << endl << w % mod << endl;
  return 0;
}
