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

#define int long long
#define db long double
#define MX LLONG_MAX
#define MN LLONG_MIN
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a / gcd(a, b) * b)

using namespace std;
using namespace __gnu_pbds;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int MOD = 1e9 + 7;

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, g;
    cin >> n >> m >> g;

    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
    }

    cout << m - n + 1 << "\n";

    int n = m;
    int k = m - n + 1;

    int ans = 1;
    for (int i = n; i > n - k; i--) {
        ans = (ans * i) % MOD;
    }

    cout << ans;
}
