Solution

第一步，我们简化题目，如果的情况下，我们如何求解个位置每个位置可选中的数，全部数乘积的和是多少。

那么这里我是一开始没看出来，所以直接暴力枚举以及的情况，根据乘法分配律还是很容易可以提出式子来的。经过提公因子可以发现，这个就会变成。

接下来我们考虑限制，如果一个位置存在限制，说明那个位置就不能选择某个数，那么它最终答案的贡献就不会是，而是去掉不能选择的数之后的和。例如第一个位置不能选择两个数，那么的情况下答案就变成。

所以答案就很容易计算了，对于数据范围来说，我们模拟每一个位置显然是会超时的，但是我们只需要模拟一下那些存在约束的位置就行了，其余位置使用快速幂就可以求解。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e5 + 7;
ll n, m, k;
map<pai, bool> mp;
map<int, int> cnt;

void solve() {
    n = read(), m = read(), k = read();
    ll tmp = n * (n + 1) / 2 % MOD;
    while (k--) {
        int x = read(), y = read();
        if (mp.count({ x,y }))    continue;
        mp[{x, y}] = 1;
        cnt[x] += y;
    }
    ll ans = qpow(tmp, m - cnt.size(), MOD);
    for (auto& it : cnt) {
        ans = ans * (tmp - it.second + MOD) % MOD;
    }
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

/*

(1,2) 3

1*1*1
1*1*2
1*2*1
1*2*2
2*1*1
2*1*2
2*2*1
2*2*2

(1*1)*(1+2)
(1*2)*(1+2)
(2*1)*(1+2)
(2*2)*(1+2)

(1+2)*(1*1+1*2+2*1+2*2)
(1+2)*(1+2)*(1+2)



(1,3) 3
1*1*1
1*1*2
1*1*3
1*2*1
1*2*2
1*2*3
1*3*1
1*3*2
1*3*3

(1*1)*(1+2+3)
(1*2)*(1+2+3)
(1*3)*(1+2+3)
(2*1)*(1+2+3)
(2*2)*(1+2+3)
(2*3)*(1+2+3)
(3*1)*(1+2+3)
(3*2)*(1+2+3)
(3*3)*(1+2+3)

(1+2+3)*(1*1+1*2+1*3+2*1+2*2+2*3+3*1+3*2+3*3)
(1+2+3)*(1*(1+2+3)+2*(1+2+3)+3*(1+2+3))
(1+2+3)*(1+2+3)*(1+2+3)


*/