construct

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;

int power(int base, int exponent) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * 1LL * base) % mod;
        }
        base = (base * 1LL * base) % mod;
        exponent /= 2;
    }
    return result;
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    if (K == 0) {
        long long result = (1LL * power(N, M)) % mod;
        cout << result << endl;
    } else {
        if (K == N) {
            if (N <= 500) {
                vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
                vector<vector<bool>> blocked(N + 1, vector<bool>(N + 1, false));

                for (int i = 0; i < K; ++i) {
                    int a, b;
                    cin >> a >> b;
                    blocked[a][b] = true;
                }

                for (int i = 1; i <= N; ++i) {
                    dp[i][1] = 1;
                }

                for (int step = 2; step <= M; ++step) {
                    for (int curShop = 1; curShop <= N; ++curShop) {
                        for (int prevShop = 1; prevShop <= N; ++prevShop) {
                            if (!blocked[prevShop][curShop]) {
                                dp[curShop][step] = (dp[curShop][step] + dp[prevShop][step - 1]) % mod;
                            }
                        }
                    }
                }

                int result = 0;
                for (int i = 1; i <= N; ++i) {
                    result = (result + dp[i][M]) % mod;
                }

                cout << result << endl;
            }
            else{
                long long result = (1LL * N * power(N - 1, M - 1)) % mod;
                cout << result << endl;
        }}
        else{
            vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
            vector<vector<bool>> blocked(N + 1, vector<bool>(N + 1, false));

            for (int i = 0; i < K; ++i) {
                int a, b;
                cin >> a >> b;
                blocked[a][b] = true;
            }

            for (int i = 1; i <= N; ++i) {
                dp[i][1] = 1;
            }

            for (int step = 2; step <= M; ++step) {
                for (int curShop = 1; curShop <= N; ++curShop) {
                    for (int prevShop = 1; prevShop <= N; ++prevShop) {
                        if (!blocked[prevShop][curShop]) {
                            dp[curShop][step] = (dp[curShop][step] + dp[prevShop][step - 1]) % mod;
                        }
                    }
                }
            }

            int result = 0;
            for (int i = 1; i <= N; ++i) {
                result = (result + dp[i][M]) % mod;
            }

            cout << result << endl;
        }
    }
    return 0;
}