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

using namespace std;
using namespace __gnu_pbds;

#define int long long
using ll = long long;

typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9 + 7;
const ll inf_ = 1e18 + 7;
const int mod = 1e9 + 7;

struct Hash {
    int mod2 = 1e9 + 7, p2 = 239;

    int sum(int a, int b) {
        a += b;
        if (a >= mod2) a -= mod2;
        return a;
    }

    int sub(int a, int b) {
        a -= b;
        if (a < 0) a += mod2;
        return a;
    }

    int mul(int a, int b) {
        return a * 1ll * b % mod2;
    }

    vector<int> h, pr;

    Hash(string s) {
        int n = s.size();
        h.resize(n);
        pr.resize(n + 1);
        h[0] = s[0];
        pr[0] = 1;
        for (int i = 1; i < n; i++)
            h[i] = sum(s[i], mul(h[i - 1], p2));
        for (int i = 1; i <= n; i++)
            pr[i] = mul(pr[i], p2);
    }

    int get(int l, int r) {
        return sub(h[r], (l ? mul(h[l - 1], pr[r - l + 1]) : 0));
    }
};

struct Fast {
    vector<vector<int>> g, gr, gc;
    vector<int> ts, col;
    vector<bool> used;

    void fts(int v) {
        used[v] = 1;
        for (auto u: g[v]) {
            if (used[u]) continue;
            fts(u);
        }
        ts.push_back(v);
    }

    vector<int> cnt;

    void paint(int v, int cl) {
        used[v] = 1;
        col[v] = cl;
        for (auto u: gr[v]) {
            if (used[u]) continue;
            paint(u, cl);
        }
    }

    void f(int v, int l, int r) {
        used[v] = 1;
        for (auto u: gc[v]) {
            if (v == l && u == r || used[u]) continue;
            f(u, l, r);
        }
    }

    int bp(int x, int n) {
        if (!n) return 1;
        if (n % 2) return x * bp(x, n - 1) % mod;
        int d = bp(x, n / 2);
        return d * d % mod;
    }

    void solve() {
        int n, m, _;
        cin >> n >> m >> _;
        g.resize(n);
        gr.resize(n);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            g[x].push_back(y);
            gr[y].push_back(x);
        }
        used.resize(n);
        for (int v = 0; v < n; v++) {
            if (!used[v])
                fts(v);
        }
        reverse(ts.begin(), ts.end());
        used.assign(n, 0);
        col.resize(n);
        int cl = 0;
        int ans = 0, kl = 1;
        for (auto v: ts) {
            if (!used[v]) {
                cnt.emplace_back();
                paint(v, cl), cl++;
            }
        }
        gr.assign(cl, {});
        gc.resize(n);
        map<pair<int, int>, int> mp;
        for (int v = 0; v < n; v++) {
            for (auto u: g[v]) {
                if (col[v] == col[u]) {
                    cnt[col[v]]++;
                    gc[v].push_back(u);
                } else {
                    mp[{col[v], col[u]}]++;
                    if (mp[{col[v], col[u]}] == 1) {
                        gr[col[v]].push_back(col[u]);
                    }
                }
            }
        }
        int R = 0;
        for (int v = 0; v < n; v++) {
            for (auto u: gc[v]) {
                used.assign(n, 0);
                f(v, v, u);
                if (!used[u]) {
                    int up = 0, down = 0;
                    for (int v1 = 0; v1 < n; v1++) {
                        if (col[v1] != col[v]) continue;
                        for (auto u1: gc[v1]) {
                            if (used[v1] && !used[u1]) down++;
                            if (!used[v1] && used[u1]) up++;
                        }
                    }
                    if (down == 1 && up == 1) R++;
                    ans++;
                }
            }
        }
        ans -= R;
        kl *= bp(2, R);/*
        for (auto c: cnt) {
            if (c) {
                kl *= c;
                kl %= mod;
                ans += c - 1;
            }
        }*/
        for (auto [e, k]: mp) {
            ans += k - 1;
            kl *= k;
            kl %= mod;
        }
        g = gr;
        gr.assign(cl, {});
        for (int v = 0; v < cl; v++) {
            for (auto u: g[v]) {
                gr[u].push_back(v);
            }
        }
        ts.clear();
        used.assign(cl, 0);
        for (int i = 0; i < cl; i++) {
            if (!used[i])
                fts(i);
        }
        reverse(ts.begin(), ts.end());
        for (int st = 0; st < cl; st++) {
            vector<int> dp(cl);
            dp[ts[st]] = 1;
            for (int v = st; v < cl; v++) {
                for (auto u: g[ts[v]]) {
                    dp[u] += dp[ts[v]];
                    dp[u] = min(dp[u], 2ll);
                }
            }
            for (auto u: g[ts[st]]) {
                if (dp[u] >= 2) {
                    ans++;
                }
            }
        }
        cout << ans << '\n' << kl;
    }
};

signed main() {
    int __ = 1;
    //cin >> __;
    while (__--) {
        Fast().solve();
        cout << '\n';
    }
    return 0;
}
