#pragma GNU optimize("O3")
#pragma GNU optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define in insert
#define int long long
#define ll long long
#define inf 1000000000000000000
#define N 2000
#define de 1000000007

vector<int> gr[N];
int cnt[N];
void tup(){
    int n, m, g; cin >> n >> m >> g;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v; u--, v--;
        if(v - 1 == u) cnt[u]++;
    }
    cout << m - (n - 1) << endl;
    int ans = 1;
    for(int i = 0; i < n - 1; i++){
        ans = ans * cnt[i] % de;
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    tup();
}