#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];

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]++;
    }
    int ans = 1;
    int sz = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (cnt[i][j] != 0 && i != j - 1) {
                sz += cnt[i][j];
            }
            else if (i == j - 1 && cnt[i][j] != 0) {
                ans *= cnt[i][j];
                sz += (cnt[i][j] - 1);
            }
            ans %= mod;
        }
    }
    cout << sz << endl << ans;
}
