// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #pragma GCC target("avx2")

using namespace std;
// using namespace __gnu_pbds;

#define int long long
// #define ordered_set tree<int, null_type, less<int>, tree_order_statistics_node_update, rb_tree_tag>

const int mod = 1e9 + 7;
mt19937_64 rnd(1329);

pair<int, int> solve_s_c(vector<vector<int>> &gr) {
    int n = gr.size();
    vector<pair<int, int>> edges;
    for (int i = 0; i < n; ++i) {
        for (auto e : gr[i]) {
            edges.push_back({i, e});
        }
    }
    vector<int> lol(n);
    for (int i = 0; i < n; ++i) lol[i] = rnd();

    int m = edges.size();
    map<int, bool> ct;
    int ans1 = 0, ans2 = 1;
    for (auto e : edges) {
        for (int i = 0; i < gr[e.first].size(); ++i) {
            if (gr[e.first][i] == e.second) {
                swap(gr[e.first][i], gr[e.first].back());
                gr[e.first].pop_back();
                break;
            }
        }
        vector<bool> used(n);
        used[e.first] = 1;
        vector<int> cur;
        cur.push_back(e.first);
        while (cur.size()) {
            int v = cur.back(); cur.pop_back();
            if (v == e.second) break;
            for (auto e : gr[v]) {
                if (!used[e]) {
                    used[e] = 1;
                    cur.push_back(e);
                }
            }
        }
        if (used[e.second]) continue;
        int hsh = 0;
        for (int i = 0; i < n; ++i) {
            if (used[i] == used[0]) {
                hsh ^= lol[i];
            }
        }
        if (ct[hsh]) {
            ans2 *= 2;
            if (ans2 >= mod) ans2 -= mod;
        }
        else {
            ans1++;
        }
        gr[e.first].push_back(e.second);
    }

    return {ans1, ans2};
}

pair<int, int> solve_single_comp(vector<int> comp, vector<vector<int>> &g) {
    map<int, int> kek;
    for (auto e : comp) kek[e] = kek.size();
    vector<vector<int>> gr(comp.size());
    for (int i = 0; i < comp.size(); ++i) {
        for (auto e : g[comp[i]]) {
            if (kek.find(e) == kek.end()) continue;
            gr[i].push_back(kek[e]);
        }
    }
    return solve_s_c(gr);
}

void solve() {
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> gr(n);
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        edges[i] = {a - 1, b - 1};
        gr[a - 1].push_back(b - 1);
    }
    vector<int> c(n);
    iota(c.begin(), c.end(), 0);
    pair<int, int> ans = solve_single_comp(c, gr);
    cout << ans.first << '\n' << ans.second << '\n';
    // vector<int> comps(n);
    // vector<int> ord;
    // vector<bool> used(n);
    // auto dfsord = [&](auto dfsord, int v) -> void {
    //     for (auto)
    // };
    // for (int i = 0; i < n; ++i) {
    //     if (used[i]) continue;

    // }
    // int ans = 0;
    // for (auto e : edges) {

    // }
    // cout << ans << "\n1\n";
}

signed main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}