设 \(h_i\) 为所有询问最大值 \(\le i\) 的方案数，则 \(ans = \dfrac{\sum\limits_{i=1}^n i \times (h_i - h_{i-1})}{x^n}\)。
设 \(g_i\) 为在 \(1 \sim n\) 中选出 \(i\) 个点且每个询问区间都至少包含一个点的方案数，则 \(h_i = \sum\limits_{j=1}^n g_j \times i^j \times (m-i)^{n-j}\)。
发现区间若包含则可以舍去较长区间，则舍去后按左端点排序，右端点也是递增的。设 \(L_i\) 为能覆盖到 \(i\) 的最左区间，\(R_i\) 为能覆盖到 \(i\) 的最右区间，\(f_{i,j}\) 表示 \(1 \sim i\) 中选了 \(j\) 个点，且 \(i\) 必须选，使得所有左端点 \(\le i\) 的区间内都有点被选的方案数，则 \(f_{i,j} = \sum\limits_{R_k + 1 \ge L_i} f_{k,j-1}\)，不难前缀和优化。那么 \(g_i = \sum\limits_{R_j = q} f_{j,i}\)。
总时间复杂度 \(O(n(n+m) \log n + q \log q)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
const ll mod = 666623333;
ll n, m, q, stk[maxn], top, L[maxn], R[maxn];
ll f[maxn][maxn], g[maxn][maxn], ff[maxn], gg[maxn];
struct node {
ll l, r;
} a[maxn];
bool cmp(node a, node b) {
return a.l < b.l || (a.l == b.l && a.r < b.r);
}
ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &q);
for (int i = 1; i <= q; ++i) {
scanf("%lld%lld", &a[i].l, &a[i].r);
}
sort(a + 1, a + q + 1, cmp);
for (int i = 1; i <= q; ++i) {
while (top && a[i].r <= a[stk[top]].r) {
--top;
}
stk[++top] = i;
}
q = top;
for (int i = 1; i <= top; ++i) {
a[i] = a[stk[i]];
}
for (int i = 1, l = 1, r = 0; i <= n; ++i) {
while (r < q && a[r + 1].l <= i) {
++r;
}
while (l <= r && a[l].r < i) {
++l;
}
L[i] = l;
R[i] = r;
}
f[0][0] = g[0][0] = 1;
for (int i = 1, k = 0; i <= n; ++i) {
while (k < i - 1 && R[k] + 1 < L[i]) {
++k;
}
for (int j = 1; j <= i; ++j) {
f[i][j] = (g[i - 1][j - 1] - (k ? g[k - 1][j - 1] : 0) + mod) % mod;
}
for (int j = 0; j <= i; ++j) {
g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
}
}
for (int i = 1; i <= n; ++i) {
if (R[i] == q) {
for (int j = 1; j <= n; ++j) {
ff[j] = (ff[j] + f[i][j]) % mod;
}
}
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
gg[i] = (gg[i] + ff[j] * qpow(i, j) % mod * qpow(m - i, n - j) % mod) % mod;
}
ans = (ans + (gg[i] - gg[i - 1] + mod) * i % mod) % mod;
}
ans = ans * qpow(qpow(m, n), mod - 2) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}