#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2007, mod = 1e9 + 7;

vector <int> v[N];
int cnt[N][N];
int used[N];

void dfs(int x) {
    if (used[x]) {
        return;
    }
    used[x] = 1;
    if (v[x].size() != 0) {
        dfs(v[x][0]);
    }
}

void dfs1(int x) {
    if (used[x] == 2) {
        return;
    }
    used[x] = 2;
    for (auto u: v[x]) {
        dfs1(u);
    }
}
signed main() {
    int n, m, g;
    cin >> n >> m >> g;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        v[x].push_back(y);
        cnt[x][y]++;
    }
    for (int i = 0; i < n; i++) {
        sort(v[i].begin(), v[i].end());
    }
    int ans = 1;
    int sz = 0;
    for (int i = 0; i < n; i++) {
        dfs(i);
        if (v[i].size() == 0) {
            continue;
        }
        for (int j = i + 1; j < n; j++) {
            if (j == v[i][0] && cnt[i][j] != 0) {
                ans *= cnt[i][j];
                sz += (cnt[i][j] - 1);
                //cout << "IJ " << i + 1 << " " << j + 1 << "   " << cnt[i][j] - 1 << endl;
            }
            else if (cnt[i][j] != 0) {
                if (used[j]) {
                    sz += cnt[i][j];
                    //cout << "IJ " << i + 1 << " " << j + 1 << " " << cnt[i][j] << endl;
                }
                else {
                    sz += (cnt[i][j] - 1);
                    ans *= cnt[i][j];
                    //cout << "IJ " << i + 1 << " " << j + 1 << " " << cnt[i][j] - 1 << endl;
                }
            }
            if (cnt[i][j] != 0) {
                dfs1(j);
            }
            ans %= mod;
        }
        fill(used, used + N, 0);
    }
    cout << sz << endl << ans;
}
