#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
// #define int long long
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//const int maxn = 2000 + 10;
//int ms[maxn][maxn];
//vector<pii> g[maxn];


void dfs1(int u, vector<vector<int>> &g, vector<int> &used, vector<int> &ts){
    used[u] = 1;
    for (int v : g[u]){
        if (!used[v]){
            dfs1(v, g, used, ts);
        }
    }
    ts.pb(u);
}


void dfs2(int u, vector<vector<int>> &g, vector<int> &color, int col){
    color[u] = col;
    for (int v : g[u]){
        if (color[v] == -1){
            dfs2(v, g, color, col);
        }
    }
}


int kond(vector<vector<int>> &g, vector<vector<int>> &rg, vector<int> &used, vector<int> &color, int n){
    used.assign(n, 0);
    color.assign(n, -1);
    vector<int> ts;
    for (int i = 0; i < n; ++i){
        if (!used[i]) dfs1(i, g, used, ts);
    }
    reverse(ts.begin(), ts.end());
    int col = 0;
    for (int i : ts){
        if (color[i] == -1){
            dfs2(i, rg, color, col++);
        }
    }
    return col;
}



void solve(){
    int n, m, gg;
    cin >> n >> m >> gg;
    vector<pii> edges;
    vector<vector<int>> start_g(n), start_rg(n);
    vector<int> start_color(n, -1), start_used(n, 0);
    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--; v--;
//        ms[u][v] = 1;
//        g[u].pb({v, i});
        edges.pb({u, v});
        start_g[u].pb(v);
        start_rg[v].pb(u);
    }
    int start_col = kond(start_g, start_rg, start_used, start_color, n);
    int ans = 0;
    int cnt = 1;
    vector<vector<int>> g(n), rg(n), g1, rg1;
    vector<int> used(n), color(n);

    for (int mask = 1; mask < (1 << m); ++mask){
        // 0 - не выключили. 1 - выключили ребро
        for (int i = 0; i < n; ++i){
            g[i].clear();
            rg[i].clear();
        }
        for (int i = 0; i < m; ++i){
            if ((1 << i) & mask){

            } else{
                int u = edges[i].first;
                int v = edges[i].second;
                g[u].pb(v);
                rg[v].pb(u);
            }
        }
        g1 = g;
        rg1 = rg;
        int sz = __builtin_popcount(mask);
        vector<int> ind(sz);
        int j = 0;
        for (int i = 0; i < m; ++i){
            if ((1 << i) & mask){
                ind[j++] = i;
            }
        }
        bool ok = 1;
        for (int rev = 0; rev < sz; ++rev){
            for (int rev1 = rev; rev1 < sz; ++rev1) {
                int msk = (1 << rev) | (1 << rev1);
                g = g1;
                rg = rg1;
                bool now_ok = 0;
                // 1 - изменили направление
                for (int i = 0; i < sz; ++i) {
                    int u = edges[ind[i]].first;
                    int v = edges[ind[i]].second;
                    if ((1 << i) & msk) {
                        g[v].pb(u);
                        rg[u].pb(v);
                    } else {
                        g[u].pb(v);
                        rg[v].pb(u);
                    }
                }
                // теперь надо сделать конденсацию

                int col = kond(g, rg, used, color, n);
                if (col != start_col) {
                    now_ok = 1;
                    //                continue;
                }
                if (now_ok) continue;
                vector<int> per(col, -1);
                for (int i = 0; i < n; ++i) {
                    if (per[color[i]] == -1) {
                        per[color[i]] = start_color[i];
                    } else if (start_color[i] != per[color[i]]) {
                        now_ok = 1;
                    }
                }
                if (now_ok) continue;
                per.assign(col, -1);
                swap(color, start_color);
                for (int i = 0; i < n; ++i) {
                    if (per[color[i]] == -1) {
                        per[color[i]] = start_color[i];
                    } else if (start_color[i] != per[color[i]]) {
                        now_ok = 1;
                    }
                }
                swap(color, start_color);

                if (now_ok == 0) ok = 0;
                if (ok == 0) break;
            }
        }
        if (ok == 1){
            if (sz > ans){
                ans = sz;
                cnt = 1;
            } else if (sz == ans){
                cnt++;
            }
        }
    }
    const int mod = 1e9 + 7;
    cout << ans << endl << cnt % mod << endl;
}



signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--){
        solve();
    }
}