#ifndef LOCAL
#pragma GCC optimize("O3")
#endif

#include <bits/extc++.h>

using namespace std;


using namespace __gnu_pbds;
using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
const ll nMax = 2000 + 228;
const ll mod = 1e9+7;
ll a[nMax];
ll diff[nMax];
ll longestway[nMax][nMax];
ll pows[nMax];
vector<int> g[nMax];
void solve() {
    pows[0]=1;
    for(int i=1;i < nMax;i++)pows[i]=(2*pows[i-1])%mod;
    ll n,m,gg;
    cin >> n >> m >> gg;
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);

    }
    for(int i =n-1;i>=0;i--){
        for(auto u : g[i]){
            longestway[i][u]=max(longestway[i][u],1ll);}
        for(auto u : g[i]){
            for(int j = i+1; j<n;j++){
                if(longestway[u][j])
                    longestway[i][j]=max(longestway[i][j],longestway[u][j]+1);
            }
        }
    }
    int amt = 0;
    for(int i = 0; i < n;i++){
        for(auto u : g[i]){
            if(longestway[i][u]>1)amt++;
        }
    }
    ll ans = 1;
    for(int i =0;i<amt;i++){
        ans*=2;
        ans%=mod;
    }
    cout << amt << ' ' << ans;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    //cin >> tt;
    while (tt--)solve();
}