// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")

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

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#ifdef LOCAL
    #define debug(x) cout << #x << ": " << x << endl;
#else
    #define debug(x)
#endif
#define mt_seed chrono::high_resolution_clock::now().time_since_epoch().count()
#define time_now chrono::high_resolution_clock::now()
#define time_res(s, f) chrono::duration_cast<chrono::nanoseconds>(f - s).count()
#define time_out(s) cout << fixed << setprecision(10) << endl << "Used: " << (ld)time_res(s, time_now) / 1e6 << " ms" << endl;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_out freopen("output.txt", "w", stdout);
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define pb push_back
#define ff first
#define sc second
#define int ll

using namespace std;
using namespace __gnu_pbds;

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using str = string;
using pii = pair<int, int>;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T1, typename T2> istream& operator>>(istream &in, pair<T1, T2> &a) { in >> a.ff >> a.sc; return in; }
#ifdef LOCAL
    template<typename T1, typename T2> ostream& operator<<(ostream &out, const pair<T1, T2> &a) { out << "{" << a.ff << ' ' << a.sc << "}"; return out; }
#else
    template<typename T1, typename T2> ostream& operator<<(ostream &out, const pair<T1, T2> &a) { out << a.ff << ' ' << a.sc; return out; }
#endif
template<typename T> istream& operator>>(istream &in, vector<T> &a) { for (auto &el : a) in >> el; return in; }
template<typename T> ostream& operator<<(ostream &out, const vector<T> &a) { for (auto &el : a) out << el << " "; return out; }
template<typename T> ostream& operator<<(ostream &out, const set<T> &a) { for (auto &el : a) out << el << " "; return out; }
template<typename T> ostream& operator<<(ostream &out, const multiset<T> &a) { for (auto &el : a) out << el << " "; return out; }
template<typename T, typename comp> ostream& operator<<(ostream &out, const unordered_set<T, comp> &a) { for (auto &el : a) out << el << " "; return out; }
template<typename T> T max(T a, T b, T c) { return max(a, max(b, c)); }
template<typename T> T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); }
template<typename T> T min(T a, T b, T c) { return min(a, min(b, c)); }
template<typename T> T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); }
const ll LOL = mt_seed;
mt19937_64 genom(LOL); ll randint(ll l, ll r) { uniform_int_distribution<ll> random_distrib_2_0(l, r); return random_distrib_2_0(genom); }
const ll RANDOM = genom(); struct chash { ll operator()(ll x) { return x ^ RANDOM; } };

const int mod = 1e9 + 7;

int n, m, G;
vector<vector<int>> g, gr;
vector<int> used;

bool dfs(int v, vector<vector<int>> &_g) {
    used[v] = 1;
    for (auto to : _g[v])
        if (used[to] == 1 || used[to] == 0 && dfs(to, _g))
            return 1;
    used[v] = 2;
    return 0;
}

bool isCycle(vector<vector<int>> &_g) {
    used.assign(n, 0);
    for (int i = 0; i < n; ++i)
        if (!used[i] && dfs(i, _g))
            return 1;
    return 0;
}

vector<int> ord;
void top_sort(int v) {
    used[v] = 1;
    for (auto to : g[v]) {
        if (!used[to])
            top_sort(to);
    }
    ord.pb(v);
}

vector<int> color;
vector<vector<int>> vert;

void dfs2(int v, vector<vector<int>> &_g) {
    used[v] = 1;
    for (auto to : _g[v])
        if (!used[to])
            dfs2(to, _g);
}
bool isFullCycle(int col, vector<vector<int>> &_g, vector<vector<int>> &_rg) {
    used.assign(n, 0);
    dfs2(vert[col][0], _g);
    for (auto el : vert[col])
        if (!used[el])
            return 0;

    dfs2(vert[col][0], _rg);
    for (auto el : vert[col])
        if (!used[el])
            return 0;
    return 1;
}

void paint(int v, int c) {
    color[v] = c;
    vert[c].pb(v);
    for (auto to : gr[v])
        if (color[to] == -1)
            paint(to, c);
}

signed main() {
    fast
#ifdef LOCAL
    file_in
#endif

    cin >> n >> m >> G;

    g.resize(n);
    gr.resize(n);
    used.resize(n);

    vector<pii> edges;

    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v; --u;
        g[v].pb(u);
        edges.pb({v, u});
    }

    for (int i = 0; i < n; ++i)
        if (!used[i])
            top_sort(i);
    reverse(all(ord));
    
    color.resize(n, -1);

    int cur = 0;
    for (int i = 0; i < n; ++i) {
        if (color[i] == -1) {
            vert.pb({});
            paint(i, cur++);
        }
    }

    vector<vector<int>> g2(cur);
    vector<pii> edges2;
    for (int i = 0; i < n; ++i) {
        for (auto to : g[i]) {
            if (color[to] != color[i]) {
                g2[color[i]].pb(color[to]);
                edges2.pb({color[i], color[to]});
            }
        }
    }

    int cnt = 0, ans = 1;

    for (int i = 0; i < sz(edges2); ++i) {
        swap(edges2[i].ff, edges2[i].sc);

        for (int j = 0; j < cur; ++j)
            g2[j].clear();
        for (auto [v, u] : edges2)
            g2[v].pb(u);

        cnt += isCycle(g2);

        swap(edges2[i].ff, edges2[i].sc);
    }

    debug(color);

    for (int col = 0; col < cur; ++col) {
        int best = 0, num = 1;
        edges2.clear();

        for (auto [v, u] : edges) {
            if (color[v] == col && color[u] == col) {
                edges2.pb({v, u});
            }
        } 

        m = sz(edges2);
        g.resize(n);
        gr.resize(n);
        for (int mask = 0; mask < (1 << m); ++mask) {
            for (auto el : vert[col]) {
                g[el].clear();
                gr[el].clear();
            }
            for (int i = 0; i < m; ++i) {
                if (mask >> i & 1) {
                    g[edges2[i].sc].pb(edges2[i].ff);
                    gr[edges2[i].ff].pb(edges2[i].sc);
                } else {
                    g[edges2[i].ff].pb(edges2[i].sc);
                    gr[edges2[i].sc].pb(edges2[i].ff);
                }
            }
            if (!isFullCycle(col, g, gr)) {
                if (best < __builtin_popcount(mask)) {
                    best = __builtin_popcount(mask);
                    num = 0;
                }
                if (best == __builtin_popcount(mask))
                    ++num;
            }
        }

        // cout << col << ": " << cnt << " | " << ans << endl;

        cnt += best;
        ans = ans * num % mod;
    }

    cout << cnt << ' ' << ans << '\n';

    return 0;
}
