#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<pair<int,int>>> g;
vector<vector<pair<int,int>>> gr;
vector<vector<pair<int,int>>> g2;
vector<vector<int>> g3;
vector<vector<pair<int,int>>> gr3;
vector<int> start;
vector<int> finish;
vector<int> len;
vector<bool> used;
vector<int> topsort;
vector<int> comp;
vector<int> si;
vector<int> inter;
vector<int> sti;
vector<int> sto;
vector<int> comp2;
ll inf = 1e9+7;
void dfs(int v) {
    used[v] = true;
    for (auto [to,num]:g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
    topsort.push_back(v);
}
void dfs2(int v,int c) {
    used[v] = true;
    comp[v] = c;
    si[c]++;
    for (auto [to,num]:gr[v]) {
        if (!used[to]) {
            dfs2(to,c);
        }
    }
}
void dfs3(int v,int num) {
    len[num]++;
    if (inter[v]) {
        finish.push_back(v);
        return;
    }
    for (auto [to,nu]:g[v]) {
        dfs3(to,num);
        break;
    }
}
int from;
int too;
void dfs4(int v,int avoid) {
    used[v] = true;
    for (auto x:g3[v]) {
        int to = finish[x];
        if (!used[to] and x!=avoid) {
            dfs4(to,avoid);
        }
    }
    if (v==too) {
        dfs4(from,avoid);
    }
    topsort.push_back(v);
}
void dfs5(int v,int avoid) {
    used[v] = true;
    //comp2[v] = c;
    for (auto [to,num]:gr3[v]) {
        if (!used[to] and num!=avoid) {
            dfs5(to,avoid);
        }
    }
    if (v==from) {
        dfs5(too,avoid);
    }
}
int main()
{
    //cin.tie(nullptr);
    //ios::sync_with_stdio(0);
    int n,m,gg;
    cin >> n >> m >> gg;
    g.resize(n);
    gr.resize(n);
    used.resize(n);
    comp.resize(n);
    si.resize(n);
    inter.resize(n);
    sti.resize(n);
    sto.resize(n);
    g3.resize(n);
    comp2.resize(n);
    gr3.resize(n);
    vector<pair<int,int>> reb;
    for (int i = 0;i < m;i++) {
        int a,b;
        cin >> a >> b;
        reb.push_back({a-1,b-1});
        g[a-1].push_back({b-1,i});
        gr[b-1].push_back({a-1,i});
        sto[a-1]++;
        sti[b-1]++;
    }
    for (int i = 0;i < n;i++) {
        if (sti[i]==0 or sto[i]==0 or sti[i]>1 or sto[i]>1) {
            inter[i] = true;
        }
    }
    for (int i = 0;i < n;i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    reverse(topsort.begin(),topsort.end());
    int cnt = 0;
    used.assign(n,0);
    for (int i = 0;i < n;i++) {
        if (!used[topsort[i]]) {
            dfs2(topsort[i],cnt++);
        }
    }
    g2.resize(cnt);
    set<pair<int,int>> reb2;
    vector<int> cou(cnt);
    for (auto [x,y]:reb) {
        if (comp[x]==comp[y]) {
            cou[comp[x]]++;
            continue;
        }
        reb2.insert({comp[x],comp[y]});
    }
    int cnt3 = 0;
    for (auto [x,y]:reb2) {
        g2[x].push_back({y,cnt3++});
    }
    ll ans = 0;
    ll num = 1;
    for (int i = 0;i < cnt;i++) {
        if (cou[i]==si[i]) {
            ans+=si[i]-1;
            num*=si[i];
            num%=inf;
        }
    }
    //used.assign(m,0);
    int cnt2 = 0;
    for (int i = 0;i < n;i++) {
        if (inter[i]) {
            for (auto [to,num]:g[i]) {
                start.push_back(i);
                len.push_back(0);
                g3[i].push_back(cnt2);
                dfs3(to,cnt2++);
            }
        }
    }
    for (auto x:g3) {
        for (auto y:x) {
            gr3[finish[y]].push_back({start[y],y});
        }
    }
    for (int i = 0;i < cnt2;i++) {
        used.assign(n,0);
        topsort.clear();
        from = start[i];
        too = finish[i];
        for (int j = 0;j < n;j++) {
            if (!used[j] and inter[j]) {
                dfs4(j,i);
            }
        }
        reverse(topsort.begin(),topsort.end());
        int cnt4 = 0;
        used.assign(n,0);
        for (int j = 0;j < topsort.size();j++) {
            if (!used[topsort[j]]) {
                cnt4++;
                dfs5(topsort[j],i);
            }
        }
        //cout << i << ' ' << len[i] << ' ' << cnt4 << '\n';
        if (cnt4!=cnt) {
            ans+=len[i];
        }
        else {
            ans+=len[i]-1;
            num*=len[i];
            num%=inf;
        }
    }
    cout << ans << ' ' << num << '\n';
    return 0;
}
