#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)((x).size()))

using ll = long long;
using ld = long double;

const ll INF = 3e18;
const ll MOD = 1e9 + 7;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> void chmax(T &a, T b) {
    if (b > a)
        a = b;
}
template <typename T> void chmin(T &a, T b) {
    if (b < a)
        a = b;
}

int bpow(int a, int e) {
    int r = 1;
    while (e) {
        if (e & 1) {
            r *= a;
            r %= MOD;
        }
        e >>= 1;
        a *= a;
        a %= MOD;
    }
    return r;
}
int inv(int a) { return bpow(a, MOD - 2); }
void solve() {
    int n, m, G;
    cin >> n >> m >> G;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
    }

    vector<bool> used(n);

    function<bool(int, pair<int, int>)> dfs = [&](auto x, const auto &y) {
        used[x] = true;

        if (x == y.second)
            return true;
        for (int u : g[x]) {
            if (used[u] || pair<int, int>{x, u} == y)
                continue;
            if (dfs(u, y))
                return true;
        }
        return false;
    };
    vector<vector<int>> ng(n);
    // vector<vector<int>> rng(n);

    int ans1 = 0;
    int ans2 = 1;
    for (int v = 0; v < n; ++v) {
        for (int u : g[v]) {
            used.assign(n, false);
            pair<int, int> no = {v, u};
            if (!dfs(v, no)) {
                // assert(abs((u-v+n)%n)==1);
                ng[v].push_back(u);
                ng[u].push_back(v);
                // cout << v + 1 << ' ' << u + 1 << '\n';

                // rng[u].push_back(v);
            }
        }
    }
    // строим на ng компоненты сильной связности
    // vector<int> order;

    // function<void(int)> find_order = [&](int v) {
    //     used[v] = true;
    //     for (int u : ng[v]) {
    //         if (!used[u]) {
    //             find_order(u);
    //         }
    //     }
    //     order.push_back(v);
    // };
    // used.assign(n, false);
    // for (int v = 0; v < n; ++v) {
    //     if (!used[v]) {
    //         find_order(v);
    //     }
    // }
    // assert(sz(order) == n);
    // reverse(all(order));
    // int C = 0;
    // used.assign(n, false);
    // vector<int> comp(n);
    // function<void(int)> mark = [&](int v) {
    //     used[v] = true;
    //     comp[v] = C;
    //     for (int u : rng[v]) {
    //         if (!used[u]) {
    //             mark(u);
    //         }
    //     }
    // };
    // for (int v : order) {
    //     if (!used[v]) {
    //         mark(v);
    //         ++C;
    //     }
    // }
    // vector<int> cnt(C);
    // for (int v = 0; v < n; ++v) {
    //     for (int u : ng[v]) {
    //         if (comp[v] == comp[u])
    //             ++cnt[comp[v]];
    //         else
    //             ++ans1;
    //     }
    // }
    // надо найти точки сочленения в ng
    int alc = 0;
    used.assign(n, false);
    function<void(int)> fd = [&](int v) {
        used[v] = true;
        for (int u : ng[v]) {
            if (!used[u]) {
                fd(u);
            }
        }
    };
    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            ++alc;
            fd(v);
        }
    }
    function<void(int, int)> fdw = [&](int v, const int &vv) {
        used[v] = true;
        for (int u : ng[v]) {
            if (!used[u] && u != vv) {
                fdw(u, vv);
            }
        }
    };
    vector<bool> dot(n);
    for (int v = 0; v < n; ++v) {
        // удаляем v
        used.assign(n, false);
        int cur = 0;
        for (int u = 0; u < n; ++u) {
            if (!used[u] && u != v) {
                ++cur;
                fdw(u, v);
            }
        }
        if (cur == alc + 1) {
            dot[v] = true;
        }
        // cout << dot[v] << ' ';
    }
    vector<int> h(n), d(n);
    map<int, int> col;
    vector<bool> pdot(n);
    function<void(int, int)> pp = [&](int v, int p) {
        used[v] = true;
        d[v] = h[v];
        int cc = 0;
        for (int u : ng[v]) {
            if (u == p)
                continue;
            if (!used[u]) {
                ++cc;
                h[u] = h[v] + 1;
                pp(u, v);
                if (d[u] >= h[v] && v != p) {
                    pdot[v] = true;
                }
                d[v] = min(d[v], d[u]);
            } else {
                d[v] = min(d[v], h[u]);
            }
        }
        if (v == p && cc > 1) {
            pdot[v] = true;
        }
    };
    vector<bool> used2(n, false);
    int curC = 0;

    function<void(int, int, int)> paint = [&](int v, int p, int cc) {
        // if (v != p) {
        //     if (d[v] >= h[v]) {
        //         ++curC;
        //         cc = curC;
        //     }
        //     col[{v, p}] = col[{p, v}] = cc;
        // }
        used2[v] = true;
        for (int u : ng[v]) {
            if (u == p)
                continue;
            if (used2[u]) {
                if (h[v] > h[u]) {
                    col[cc]++;
                }
            } else {
                if (v == p) {
                    ++curC;
                    col[curC]++;
                    paint(u, v, curC);
                } else {
                    if (dot[v] && d[u] >= h[v]) {
                        ++curC;
                        col[curC]++;

                        paint(u, v, curC);
                    } else {
                        col[cc]++;

                        paint(u, v, cc);
                    }
                }
            }
        }
    };
    used.assign(n, false);

    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            pp(v, v);
            paint(v, v, ++curC);
        }
    }
    assert(pdot == dot);

    for (auto [x, y] : col) {
        if (y == 1) {
            ans1 += 1;
        } else {
            ans1 += y - 1;
            ans2 *= y;
        }

        ans2 %= MOD;
    }
    cout << ans1 << ' ' << ans2 << '\n';
}

signed main() {
#ifdef LOCALEGOR
    freopen("INPUT.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }
}
