#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 1e9 + 7;

vector<int> factmod;
vector<int> fomod;

int cnk(int k, int n) {
    return (((factmod[n] * fomod[k]) % MOD) * fomod[n - k]) % MOD;
}

bool is_d(int i, int v, vector<vector<int>> &gr, vector<bool> &used, int st) {
    if (used[i]) return false;
    used[i] = true;
    if (i == v) return true;
    for (auto &j : gr[i]) {
        if (i == st && j == v) continue;
        if (is_d(j, v, gr, used, st)) return true;
    }
    return false;
}

int ansdag(vector<vector<int>> &gr) {
    int n = gr.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            vector<bool> used(n, false);
            if (is_d(i, j, gr, used, i)) {
                ans++;
            }
        }
    } 
    return ans;
}

void dfs(int i, vector<vector<int>> &gr, vector<bool> &used) {
    if (used[i]) return;
    used[i] = true;
    for (auto &j : gr[i]) dfs(j, gr, used);
}

pair<int, int> ans_comp(vector<vector<int>> &gr) {
    int n = gr.size();
    //vector<vector<int>> gr2(n);
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            vector<bool> used(n, false);
            if (!is_d(i, j, gr, used, i)) {
                cnt++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            vector<bool> used(n, false);
            if (!is_d(i, j, gr, used, i)) {
                ans++;
                gr[j].push_back(i);
            }
        }
    }
    return {ans, cnk(ans, cnt)};
}

pair<int, int> ans(vector<vector<int>> &gr, int g) {
    int n = gr.size();
    vector<vector<bool>> d(n, vector<bool> (n, false));
    for (int i = 0; i < n; i++) {
        dfs(i, gr, d[i]);
    }
    //assert(false);
    vector<vector<int>> comps(0);
    vector<int> c(n, -1), comp_ind(n, -1);
    for (int i = 0; i < n; i++) {
        if (c[i] != -1) continue;
        int cur_comp = comps.size();
        comps.push_back(vector<int> (0));
        for (int j = i; j < n; j++) {
            if (d[i][j] && d[j][i]) {
                comp_ind[j] = comps[cur_comp].size();
                c[j] = cur_comp;
                comps[cur_comp].push_back(j);
            }
        }
    }
    int fans = 0;
    vector<vector<int>> gr2(comps.size());
    set<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            assert(c[i] != -1);
            assert(c[j] != -1);
            assert(comp_ind[i] != -1);
            assert(comp_ind[j] != -1);
            if (c[i] != c[j]) {
                assert(!(d[i][j] && d[j][i]));
                if (s.find(make_pair(c[i], c[j])) != s.end()) {
                    fans++;
                } else {
                    gr2[c[i]].push_back(c[j]);
                    s.insert({c[i], c[j]});
                }
            }
        }
    }
    fans += ansdag(gr2);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (c[i] == c[j]) {
                assert((d[i][j] && d[j][i]));
            } else {
                assert(!(d[i][j] && d[j][i]));
            }
        }
    }
    for (int i = 0; i < n; i++) {
        assert(comps[c[i]][comp_ind[i]] == i);
    }
    int fans2 = 1;
    for (int cmp = 0; cmp < comps.size(); cmp++) {
        vector<vector<int>> gr3(comps[cmp].size());
        for (auto &i : comps[cmp]) {
            for (auto &j : gr[i]) {
                if (c[j] != cmp) continue;
                gr3[comp_ind[i]].push_back(comp_ind[j]);
            }
        }
        auto tmp =  ans_comp(gr3);
        fans += tmp.first;
        fans2 *= tmp.second;
        fans2 %= MOD;
    }
    return {fans, fans2};
}

int binup(int a, int st) {
    if (st == 0) return 1;
    if (st % 2) return (binup(a, st - 1) * a) % MOD;
    return binup((a * a) % MOD, st / 2);
}

main() {
    factmod.resize(1e4);
    fomod.resize(1e4);
    factmod[0] = 1;
    for (int i = 1; i < 1e4; i++) {
        factmod[i] = (factmod[i - 1] * i) % MOD;
    }
    fomod[1e4 - 1] = binup(factmod[1e4 - 1], MOD - 2);
    for (int i = 1e4 - 2; i >= 0; i--) {
        fomod[i] = (fomod[i + 1] * (i + 1)) % MOD;
        
    }
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> gr(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        gr[u].push_back(v);
    }
    auto lans = ans(gr, g);
    cout << lans.first << " " << lans.second << "\n";
    //cout << ansdag(gr) << " " << 1 << "\n";
}