#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define all(vec) vec.begin(), vec.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll

mt19937_64 rnd;

ll INF = 1e9;
ll mod = 1e9+7;

vector<vector<int>> g;
vector<vector<int>> gr;
vector<int> used;

vector<int> tp;
vector<int> cp;
vector<int> dist;
vector<int> calc;
vector<int> sz;

int comp = 1;

vector<vector<int>> new_g;


void topsort(int v) {
    used[v] = 1;
    for (auto now : g[v]) {
        if (!used[now]) topsort(now);
    }
    tp.push_back(v);
}

void dfs(int v) {
    cp[v] = comp;
    sz[comp]++;
    for (auto now : gr[v]) {
        if (!cp[now]) dfs(now);
    }
}

void dfs2(int v) {
    used[v] = 1;
    for (auto now : g[v]) {
        if (cp[v] != cp[now] && used[now] != 1) {
            dist[cp[now]]++;
        }
        if (!used[now]) dfs2(now);
    }
    used[v] = 2;
}

void solve() {
    ll n, m, G;
    cin >> n >> m >> G;
    g.resize(n + 1);
    gr.resize(n + 1);
    used.resize(n + 1);
    cp.resize(n + 1);
    dist.resize(n + 1);
    //calc.resize(n + 1);
    sz.resize(n + 1);
    new_g.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        gr[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) topsort(i);
    }
    reverse(all(tp));
    used.assign(n + 1, 0);
    for (auto now : tp) {
        if (!cp[now]) {
            dfs(now);
            comp++;
        }
    }
    //for (int i = 1; i <= n; i++) cout << cp[i] << " ";
    ll ans = 0;
    ll k = 1;
    //cout << "OK\n";
    ll cl = 0;

    for (int i = 1; i <= n; i++) {
        dfs2(i);

        for (auto now : g[i]) {
            if (cp[i] != cp[now]) {
                if (dist[cp[now]] != 1) cl++;
            } else {

            }
        }
        dist.assign(n + 1, 0);
    }
    for (int i = 1; i < comp; i++) {
        ans += sz[i] - 1;
        k = (k * sz[i]) % mod;
    }
    if (cl != 0) {
        ans++;
        //k = (k * cl) % mod;
    }
    cout << ans << "\n" << k << "\n";
}

signed main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
