#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<ll>> g, rg;
vector<ll> us;
vector<ll> clr;
vector<ll> ord, d;
vector<vector<ll>> cmp;
vector<vector<ll>> cg;
void rdfs(ll v) {
    if (us[v]) return;
    us[v] = 1;
    for (auto u : rg[v]) rdfs(u);
    ord.push_back(v);
}
void cdfs(ll v, ll c) {
    if (us[v]) return;
    us[v] = 1;
    clr[v] = c;
    cmp.back().push_back(v);
    for (auto u : g[v]) cdfs(u, c);
}
void adfs(ll v) {
    for (int i : cg[v]) {
        if (d[i] < 2) {
            d[i] = d[v] + 1;
            adfs(i);
        }
    }
}

int main() {
    ll n, m, t;
    cin >> n >> m >> t;
    g.resize(n);
    rg.resize(n);
    for (int i = 0; i < m; i++) {
        ll u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    us.assign(n, 0);
    for (int i = 0; i < n; i++) rdfs(i);
    reverse(ord.begin(), ord.end());
    int k = 0;
    us.assign(n, 0);
    clr.assign(n, 0);
    for (int i : ord) {
        if (us[i] == 0) {
            cmp.push_back({});
            cdfs(i, k++);
        }
    }
    //cout << 9 << endl;
    cg.resize(k);
    vector<vector<int>> bg(k, vector<int>(k));
    for (int i = 0; i < n; i++) {
        for (auto j : g[i]) {
            if (clr[i] != clr[j]) {
                cg[clr[i]].push_back(clr[j]);
                bg[clr[i]][clr[j]]++;
            }
        }
    }
    ll ans = 0;
    ll cnt = 1;
    ll P = 1e9 + 7;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (bg[i][j]) {
                d.assign(k, 0);
                adfs(i);
                if (d[j] >= 2) {
                    ans += bg[i][j];
                } else {
                    ans += bg[i][j] - 1;
                    cnt *= bg[i][j];
                    cnt %= P;
                }
            }
        }
    }
    //cout << k << endl;
    cout << ans << "\n" << cnt << endl;
}