#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 2e5 + 1;
const int inf = 4e18;

void solve() {
    int n, m, gg;
    cin >> n >> m >> gg;
    vector<vector<int>> g(n);
    vector<pair<int, int>> edges;
    int tt = 0;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        if (v != u - 1) {
            tt++;
        }
        edges.emplace_back(v, u);
        g[v].push_back(u);
    }

    vector<int> order;
    vector<int> comp(n, 0);
    vector<int> used(n, false);
    function<bool(int, int)> dfs = [&](int v, int st) {
        used[v] = true;
        order.push_back(v);
        for (int u: g[v]) {
            if (!used[u]) {
                if (dfs(u, st)) return true;
            } else if (u == st) {
                while (!order.empty()) {
                    int s = order.back();
                    comp[s] = comp[st];
                    order.pop_back();
                }
                return true;
            }
        }
        order.pop_back();
        return false;
    };

    function<int()> calc = [&]() {
        int cnt = 1;
        comp.assign(n, 0);
        for (int v = 0; v < n; v++) {
            if (!comp[v]) {
                comp[v] = cnt++;
                used.assign(n, false);
                order.clear();
                dfs(v, v);
            }
        }
        set<int> p;
        for (int x: comp) {
            p.insert(x);
        }
        return p.size();
    };

//    int good = calc();
////    cout << good << '\n';
//    int ans = 0;
//    int cntans = 0;
//    vector<vector<int>> dp(1 << m, vector<int>(m));
//    for (int j = 0; j < m; j++) {
//        int mask = 1 << j;
//        g.assign(n, vector<int>());
//        for (int bit = 0; bit < m; bit++) {
//            auto [v, u] = edges[bit];
//            if (bit == j) {
//                g[u].push_back(v);
//            } else {
//                g[v].push_back(u);
//            }
//        }
//        int ncalc = calc();
//        if (ncalc != good) {
//            dp[mask][j] = true;
//            cout << j << '\n';
//        }
//    }
//    for (int mask = 0; mask < (1 << m); mask++) {
//        for (int i = 0; i < m; i++) {
//            if ((mask >> i) & 1 and dp[mask ^ (1 << i)][i]) {
//                g.assign(n, vector<int>());
//                for (int bit = 0; bit < m; bit++) {
//                    auto [v, u] = edges[bit];
//                    if ((mask >> bit) & 1) {
//                        g[u].push_back(v);
//                    } else {
//                        g[v].push_back(u);
//                    }
//                }
//
//                int ncalc = calc();
//                if (ncalc != good) {
//                    int t = __builtin_popcount(mask);
//                    if (t == ans) cntans++;
//                    else if (t < ans) {
////                cout << mask << ' ' << ncalc << '\n';
////                cout << t << '\n';
//                        ans = t;
//                        cntans = 1;
//                    }
//                }
//            }
//        }
//
//    }
    int p = 1;
    for (int i = 1; i < tt; i++) {
        p = (p * i) % mod;
    }
    cout << tt << ' ' << p << '\n';
}

signed main() {
#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
//    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}
