#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3")

using namespace std;
//using namespace __gnu_pbds;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define int long long

//typedef tree<int, null_type,less<int>,  rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int mod = (int)1e9 + 7;

signed main(){
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int n, m, cucumber;
    cin>>n>>m>>cucumber;
    vector<vector<int> > g(n), gr(n);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin>>a>>b;
        --a; --b;
        g[a].push_back(b);
        gr[b].push_back(a);
    }
    vector<int> top, used(n);
    int col = 1;
    auto dfs = [&](auto self, int v) -> void{
        used[v] = col;
        for(int u:g[v]){
            if (!used[u]){
                self(self, u);
            }
        }
        top.push_back(v);
    };
    for(int i = 0; i< n; ++i){
        if (!used[i]){
            dfs(dfs, i);
        }
    }
    reverse(top.begin(), top.end());
    used.assign(n, 0);
    auto dfs1 = [&](auto self, int v) -> void{
        used[v] = col;
        for(int u:gr[v]){
            if (!used[u]){
                self(self, u);
            }
        }
    };
    for(int i:top){
        if(!used[i]){
            dfs1(dfs1, i);
            ++col;
        }
    }
    vector<vector<int> > tr(col);
    map<int, int> sz;
    vector<pair<int,int> > ee;
    for(int i = 0; i< n; ++i){
        ++sz[used[i]];
        for(int u:g[i]){
            if (used[i] != used[u]){
                tr[used[i]].push_back(used[u]);
                ee.emplace_back(used[i], used[u]);
            }
        }
    }
    int ans = 1;
    int res = 0;
    for(auto &[l,r]:sz){
        ans = (ans * r)%mod;
        if (r > 1){
            res += 2;
        }
    }
    vector<pair<int,int> > ne;

    vector<vector<int> > t, trr;

    auto ok = [&]() -> bool{
        t.clear();
        t.resize(col);
        trr.clear();
        trr.resize(col);
        for(auto &[u,v]:ne){
            t[u].push_back(v);
            trr[v].push_back(u);
        }
        used.assign(col, 0);
        top.clear();
        int ww = 1;
        auto dfs = [&](auto self, int v) -> void{
            used[v] = 1;
            for(int u:t[v]){
                if (!used[u]){
                    self(self, u);
                }
            }
            top.push_back(v);
        };
        for(int i = 1; i < col; ++i){
            if (!used[i]){
                dfs(dfs, i);
            }
        }
        reverse(top.begin(), top.end());
        used.assign(col, 0);
        auto dfs1 = [&](auto self, int v) -> void{
            used[v] = ww;
            for(int u:trr[v]){
                if (!used[u]){
                    self(self, u);
                }
            }
        };
        for(int i:top){
            if(!used[i]){
                dfs1(dfs1, i);
                ++ww;
            }
        }
        return ww == col;
    };
    int op = 0;
    for(int i = 0; i < ee.size(); ++i){
        ne.clear();
        for(int j = 0; j < ee.size(); ++j){
            if (j == i){
                ne.emplace_back(ee[j].second, ee[j].first);
            }
            else{
                ne.push_back(ee[j]);
            }
        }
        if (!ok()){
            ++op;
        }
    }
    cout<<res+op<<'\n'<<ans<<'\n';
    return 0;
}
