#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
// #define int long long
const int MOD = 1e9 + 7;
int add(int a,int b){
    if(a+b<MOD){
        return a+b;
    }
    return a+ b -MOD;
}
int sub(int a,int b){
    if(a - b < 0){
        return a - b +MOD;
    }
    return a - b;
}
int mult(int a,int b){
    return (ll)((ll)a * (ll)b)%MOD;
}
const int N = 2e3 + 100;
// int binpow(int a,int m){
//     if(m==0){
//         return 1;
//     }else if(m%2==1){
//         return mult(a,binpow(a,m-1));
//     }else{
//         int x = binpow(a,m/2);
//         return mult(x,x);
//     }
// }
// int fact[N];

vector<int> g[N], gr[N];
vector<int> order;
bool used[N];
void topsort(int v){
    used[v] = true;
    for(int u:g[v]){
        if(!used[u]){
            topsort(u);
        }
    }
    order.pb(v);
}
int a[N];
int cnt = 0;
void dfs(int v){
    a[v] = cnt;
    for(int u:gr[v]){
        if(a[u] == 0){
            dfs(u);
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // fact[0] = 1;
    // for(int i=1;i<N;++i){
    //     fact[i] = mult(fact[i-1],i);
    // }
    int testnum;
    int n, m;
    cin >> n >> m >> testnum;
    for(int i=0;i<m;++i){
        int v, u;
        cin >> v >> u;
        g[v].pb(u);
        gr[u].pb(v);
    }
    for(int i=1;i<=n;++i){
        if(!used[i]){
            topsort(i);
        }
    }
    reverse(all(order));
    // for(int i:order){
    //     if(a[i] == 0){
    //         ++cnt;
    //         dfs(i);
    //     }
    // }
    int ans = 1;
    for(int i:order){
        if (i == order[0]){
            continue;
        }
        ans = mult(ans,(int)gr[i].size());
    }
    cout << m - (n-1) << " " << 1;
    return 0;
}