#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;

void dfs(int v, vector<int> &used, vector<vector<int>> &g, vector<int> &ord) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs(u, used, g, ord);
        }
    }
    ord.push_back(v);
}

void color(int v, int color_nw, vector<int> &colors, vector<vector<int>> &_g) {
    colors[v] = color_nw;
    for (auto u : _g[v]) {
        if (colors[u] == -1) {
            color(u, color_nw, colors, _g);
        }
    }
}

pair<int, vector<int>> get_dug(int n, vector<vector<int>> g) {
    vector<int> used(n);
    vector<int> ord;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, used, g, ord);
        }
    }
    vector<vector<int>> _g(n);
    for (int i = 0; i < n; ++i) {
        for (auto j : g[i]) {
            _g[j].push_back(i);
        }
    }
    reverse(ord.begin(), ord.end());
    vector<int> colors(n, -1);
    int cnt_colors = 0;
    for (auto v : ord) {
        if (colors[v] == -1) {
            color(v, cnt_colors, colors, _g);
            cnt_colors++;
        }
    }
    return make_pair(cnt_colors, colors);
}

void solve() {
    int n, m, subtask;
    cin >> n >> m >> subtask;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
    }
    auto [cnt_colors, colors] = get_dug(n, g);
    vector<vector<pair<int, int>>> g2(cnt_colors);
    for (int i = 0; i < n; ++i) {
        for (auto j : g[i]) {
            if (colors[i] != colors[j]) {
                g2[colors[i]].emplace_back(colors[j], i * n + j);
            }
        }
    }
    auto count = [&](int v, int blocked) -> int {
        vector<int> used(cnt_colors);
        queue<int> q;
        q.push(v);
        used[v] = 1;
        int ans = 1;
        while (!q.empty()) {
            int nw = q.front();
            q.pop();
            for (auto [nxt, ind] : g2[nw]) {
                if (!used[nxt] && ind != blocked) {
                    q.push(nxt);
                    used[nxt] = 1;
                    ans++;
                }
            }
        }
        return ans;
    };
    int ans1 = 0, ans2 = 1;
    for (int i = 0; i < cnt_colors; ++i) {
        int cnt_all = count(i, -1);
        for (auto [j, ind] : g2[i]) {
            if (count(i, ind) == cnt_all) {
                ans1++;
            }
        }
    }
    vector<vector<int>> vss(cnt_colors);
    for (int i = 0; i < n; ++i) {
        vss[colors[i]].push_back(i);
    }
    for (auto vs : vss) {
        int cnt_nw = vs.size();
        vector<pair<int, int>> edges;
        set<pair<int, int>> s;
        int pos1 = 0;
        for (auto v : vs) {
            for (auto u : g[v]) {
                if (colors[u] == colors[v]) {
                    int pos2 = lower_bound(vs.begin(), vs.end(), u) - vs.begin();
                    edges.emplace_back(pos1, pos2);
                    s.emplace(pos1, pos2);
                }
            }
            pos1++;
        }
        while (!s.empty()) {
            auto [u, v] = *s.begin();
            s.erase(make_pair(u, v));
            vector<vector<int>> g3(cnt_nw);
            for (auto [a, b] : edges) {
                if (a != u || b != v) {
                    g3[a].push_back(b);
                }
            }
            auto [cnt_colors_nw, colors_nw] = get_dug(cnt_nw, g3);
            if (cnt_colors_nw == 1) {
                continue;
            }
            vector<vector<pair<int, int>>> g4(cnt_colors_nw);
            for (int i = 0; i < cnt_nw; ++i) {
                for (auto j : g3[i]) {
                    if (colors_nw[i] != colors_nw[j]) {
                        s.erase(make_pair(i, j));
                        g4[colors_nw[i]].emplace_back(colors_nw[j], i * cnt_nw + j);
                    }
                }
            }
            int st = colors_nw[v], fn = colors_nw[u];
            auto check_without_edge = [&](int a, int b, int blocked) -> bool {
                vector<int> used(cnt_colors_nw);
                used[a] = 1;
                queue<int> q;
                q.push(a);
                while (!q.empty()) {
                    int v = q.front();
                    q.pop();
                    for (auto [u, ind] : g4[v]) {
                        if (!used[u] && ind != blocked) {
                            if (u == b) {
                                return true;
                            }
                            used[u] = 1;
                            q.push(u);
                        }
                    }
                }
                return false;
            };
            int cnt1 = 0, cnt2 = 0;
            for (int i = 0; i < cnt_colors_nw; ++i) {
                for (auto [j, ind] : g4[i]) {
                    if (!check_without_edge(st, j, ind) || !check_without_edge(i, fn, ind)) {
                        cnt1++;
                    } else {
                        cnt2++;
                    }
                }
            }
            if (cnt2 > 0) {
                ans1 += cnt1 + 1;
            } else {
                ans1 += cnt1;
                ans2 = ans2 * 1LL * (cnt1 + 1) % MOD;
            }
        }
    }
    cout << ans1 << '\n';
    cout << ans2 << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
