// tch1cherin 2405
// GOLD GOLD GOLD GOLD GOLD!
// tch1cherin 2405
// GOLD GOLD GOLD GOLD GOLD!
// tch1cherin 2405
// GOLD GOLD GOLD GOLD GOLD!
#ifdef LOCAL_JUDGE
// #define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
#pragma GCC target("avx2,tune=native")
using namespace std;

constexpr int MAX_N = 2000;

vector<int> graph[MAX_N], rev_graph[MAX_N];
vector<int> topsort;
bool used[MAX_N];
vector<int> comp;

void dfs(int u) {
  used[u] = true;
  for (int v : graph[u]) {
    if (!used[v]) {
      dfs(v);
    }
  }
  topsort.push_back(u);
}

void color_dfs(int u, int c) {
  comp[u] = c;
  for (int v : rev_graph[u]) {
    if (comp[v] == -1) {
      color_dfs(v, c);
    }
  }
}

pair<int, vector<int>> find_scc(vector<array<int, 2>> edges, int n, int e) {
  fill(used, used + n, false);
  for (int i = 0; i < n; i++) {
    graph[i] = rev_graph[i] = {};
  }
  topsort.clear();
  for (int i = 0; i < int(edges.size()); i++) {
    if (i == e) {
      graph[edges[i][1]].push_back(edges[i][0]);
      rev_graph[edges[i][0]].push_back(edges[i][1]);
    } else {
      graph[edges[i][0]].push_back(edges[i][1]);
      rev_graph[edges[i][1]].push_back(edges[i][0]);
    }
  }
  for (int i = 0; i < n; i++) {
    if (!used[i]) {
      dfs(i);
    }
  }
  reverse(topsort.begin(), topsort.end());
  comp.assign(n, -1);
  int total = 0;
  for (int i : topsort) {
    if (comp[i] == -1) {
      color_dfs(i, total++);
    }
  }
  return {total, comp};
}

// IMPORTANT: MAKE A SEPARATE FILE FOR EACH SOLUTION!
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, g;
  cin >> n >> m >> g;
  vector<array<int, 2>> edges(m);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    --u, --v;
  }
  auto [scc_count, sccs] = find_scc(edges, n, -1);
  vector<int> counts(n);
  int num_edges = 0;
  for (int e = 0; e < m; e++) {
    auto [scc_e_count, sccs_e] = find_scc(edges, n, e);
    if (scc_count != scc_e_count) {
      auto [u, v] = edges[e];
      if (sccs[u] == sccs[v]) {
        ++counts[sccs[u]];
      } else {
        ++num_edges;
      }
    }
  }
  constexpr int MOD = 1e9 + 7;
  int ways = 1;
  for (int i = 0; i < n; i++) {
    if (counts[i] != 0) {
      ways = 1LL * ways * counts[i] % MOD;
      ++num_edges;
    }
  }
  cout << num_edges << "\n" << ways << "\n";
}
// go go go alena13
// go go go alena13
// go go go alena13
