// #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();
            // cout << v << '\n';
            if (v == e.second) break;
            for (auto e : gr[v]) {
                if (!used[e]) {
                    used[e] = 1;
                    cur.push_back(e);
                }
            }
        }
        gr[e.first].push_back(e.second);
        if (used[e.second]) continue;
        gr[e.second].push_back(e.first);
        ans1++;
        continue;
        int hsh = 0;
        for (int i = 0; i < n; ++i) {
            if (used[i] == used[0]) {
                hsh ^= lol[i];
            }
        }
        // cout << e.first << ' ' << e.second << ' ' << hsh << '\n';
        // for (auto e : used) cout << e << ' '; cout << '\n';
        if (ct[hsh]) {
            ans2 *= 2;
            if (ans2 >= mod) ans2 -= mod;
        }
        else {
            ans1++;
        }
    }

    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);
}

vector<int> comps(vector<vector<int>> &gr) {
    int n = gr.size();
    vector<int> ord;
    vector<bool> used(n);
    auto dfs = [&](auto dfs, int v) -> void {
        used[v] = 1;
        for (auto e : gr[v]) {
            if (used[e]) continue;
            dfs(dfs, e);
        }
        ord.push_back(v);
    };
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        dfs(dfs, i);
    }
    reverse(ord.begin(), ord.end());
    vector<vector<int>> rgr(n);
    for (int i = 0; i < n; ++i) {
        for (auto e : gr[i]) {
            rgr[e].push_back(i);
        }
    }
    vector<int> ans(n);
    int curc = 0;
    used.clear(); used.resize(n);
    for (auto i : ord) {
        if (used[i]) {
            continue;
        }
        curc++;
        vector<int> cur;
        cur.push_back(i);
        used[i] = 1;
        while (cur.size()) {
            int v = cur.back(); cur.pop_back();
            ans[v] = curc;
            for (auto e : rgr[v]) {
                if (used[e]) continue;
                used[e] = 1;
                cur.push_back(e);
            }
        }
    }
    return ans;
}

int solve_kek(vector<vector<int>> gr) {
    int n = gr.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        sort(gr[i].begin(), gr[i].end());
        vector<bool> used(n);
        used[i] = 1;
        for (auto e : gr[i]) {
            if (used[e]) {
                ans++;
                continue;
            }
            vector<int> cur;
            cur.push_back(e);
            used[e] = 1;
            while (cur.size()) {
                int v = cur.back();
                cur.pop_back();
                for (auto e : gr[v]) {
                    if (!used[e]) {
                        used[e] = 1;
                        cur.push_back(e);
                    }
                }
            }
        }
    }
    return ans;
}

int solve_lol(vector<vector<int>> &gr, vector<int> &c) {
    int n = gr.size();
    vector<vector<int>> ngr(*max_element(c.begin(), c.end()) + 1);
    vector<vector<bool>> used(n, vector<bool>(n));
    for (int i = 0; i < n; ++i) used[i][i] = 1;
    for (int i = 0; i < n; ++i) {
        for (auto e : gr[i]) {
            if (!used[c[i]][c[e]]) {
                ngr[c[i]].push_back(c[e]);
            }
        }
    }
    return solve_kek(ngr);
}

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 = comps(gr);
    for (auto &e : c) --e;
    // for (auto e : c) cout << e << ' ';
    int ans = solve_lol(gr, c);
    int T = *max_element(c.begin(), c.end());
    vector<vector<int>> cmps(T + 1);
    for (int i = 0; i < n; ++i) cmps[c[i]].push_back(i);
    for (auto e : cmps) ans += solve_single_comp(e, gr).first;
    cout << ans << "\n0\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();
}