#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;

int add(int a, int b) {
    return a + b >= mod ? a + b : a + b - mod;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}
int mult(int a, int b) {
    return a * 1ll * b % mod;
}
int bpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mult(ans, a);
        a = mult(a, a);
        b >>= 1;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, m, G;
    cin >> n >> m >> G;

    int cc = 0;
    
    vector<int> bamboo;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);

        if (u != v - 1) {
            cc++;
        }

        if (u == v - 1) {
            bamboo.push_back(u);
        }
    }

    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }
    sort(bamboo.begin(), bamboo.end());

    if (G == 3) {
        cout << cc << "\n";
        cout << 1 << "\n";
    } else if (G == 4) {
        vector<pair<int, int>> bam;
        for (int i = 0; i < bamboo.size(); ) {
            int st = bamboo[i];
            int prev = bamboo[i];
            while (i < n && prev == bamboo[i]) {
                prev = bamboo[i] + 1;
                ++i;
            }
            bam.push_back({st, prev});
        }

        int ans = 0;
        for (auto& u: bam) {
            for (int i = u.first; i <= u.second; ++i) {
                int cnt = upper_bound(g[i].begin(), g[i].end(), u.second) - lower_bound(g[i].begin(), g[i].end(), i + 2);
                ans = add(ans, cnt);
            }
        }

        cout << ans << "\n";
        cout << 1 << "\n";
    } else {
        return 0;
    }

    return 0;
}
