#include "bits/stdc++.h"
#pragma GCC optimize("unroll-loops", "Ofast")
using namespace std;
#define ll long long
const int inf = 2e9;
const ll INF = 2e18;

//#define int ll
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
typedef tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

random_device dev;
mt19937 rnd(dev());

template<typename T1, typename T2>
istream& operator >> (istream &in, pair<T1, T2> &a) {
    in >> a.first >> a.second;
    return in;
}

template<typename T1, typename T2>
ostream& operator << (ostream &out, pair<T1, T2> &a) {
    out << a.first << " " << a.second;
    return out;
}

template<typename T>
istream& operator >> (istream &in, vector<T> &a) {
    for (int i = 0; i < a.size(); i++)
        in >> a[i];
    return in;
}

template<typename T>
ostream& operator << (ostream &out, vector<T> &a) {
    for (auto &i: a)
        cout << i << " ";
    return out;
}

template<typename T>
T msMx(multiset<T> &ms) {
    auto it = ms.end();
    it--;
    return *it;
}

const ll MOD = 1e9 + 7;

ll modPw(ll a, ll n) {
    ll res = 1;
    for (; n > 0; n /= 2, a = (a * a) % MOD) {
        if (n & 1)
            res = (res * a) % MOD;
    }
    return res;
}


vector<vector<pair<int, int>>> g, rg;
vector<int> used;
vector<int> topsort;
void dfs(int v, int stop) {
    used[v] = true;
    for (auto [u, e]: rg[v]) {
        if (used[u] || e == stop)
            continue;
        dfs(u, stop);
    }
    topsort.push_back(v);
}

vector<int> color;
vector<int> ecolor;
void cdfs(int v, int c, bool change, int stop) {
    color[v] = c;
    for (auto [u, e]: g[v]) {
        if (color[u] == color[v] && change)
            ecolor[e] = c;
        if ((color[u] == -1) && (e != stop)) {
            cdfs(u, c, change, stop);
            if (change)
                ecolor[e] = c;
        }
    }
}

int n, m;

vector<pair<int, int>> edges;
void calcColor(int e) {
    if (e != -1) {
        g[edges[e].second].push_back({edges[e].first, -1});
        rg[edges[e].first].push_back({edges[e].second, -1});
    }
    topsort.clear();
    used.assign(n, false);
    color.assign(n, -1);
    for (int i = 0; i < n; i++) {
        if (!used[i])
            dfs(i, e);
    }
    int cur = 0;
    reverse(topsort.begin(), topsort.end());
    for (int i: topsort) {
        if (color[i] == -1) {
            cdfs(i, cur, e == -1, e);
            cur++;
        }
    }
    if (e != -1) {
        g[edges[e].second].pop_back();
        rg[edges[e].first].pop_back();
    }
    vector<int> tmp(cur, -1);
    for (int i = 0; i < n; i++) {
        if (tmp[color[i]] == -1) {
            tmp[color[i]] = i;
        }
        color[i] = tmp[color[i]];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> n >> m >> _;
    g.resize(n);
    rg.resize(n);
    used.assign(n, false);
    color.assign(n, -1);
    ecolor.assign(m, -1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back({v, i});
        rg[v].push_back({u, i});
        edges.push_back({u, v});
    }

    calcColor(-1);
    ll ans = 0;

    auto fc = color;
    int cntC = 0;
    for (int i = 0; i < m; i++)
        cntC = max(cntC, ecolor[i] + 1);
    vector<int> cnt(cntC, 0);
    for (int i = 0; i < m; i++) {
        calcColor(i);
        bool flag = true;
        for (int j = 0; j < n; j++) {
            if (color[j] != fc[j]) {
                flag = false;
                break;
            }
        }
        if (!flag) {
            if (ecolor[i] == -1)
                ans++;
            else
                cnt[ecolor[i]]++;
        }
    }

    ll res = 1;

    for (int i = 0; i < cntC; i++) {
        if (cnt[i] >= 1) {
            res = (res * cnt[i]) % MOD;
            ans += cnt[i] - 1;
        }
    }
    cout << ans << "\n" << res;
}
