// luogu3600

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=2010,MOD=666623333;

int n,m,X,Q;

LL f[maxn],s[maxn],inv[maxn],ans;

struct data {int l,r;}q[maxn],t[maxn];

bool cmp(data a,data b) {

	return a.l==b.l ? a.r<b.r : a.l<b.l;

}

LL power(LL a,LL b) {

	LL res=1;

	while (b) {

		if (b&1) (res*=a)%=MOD;

		b>>=1;(a*=a)%=MOD;

	}

	return res;

}

int main() {

	scanf("%d%d%de",&n,&X,&Q);

	for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r);

	sort(q+1,q+1+Q,cmp);

	for (int i=1;i<=Q;i++) {

		while (q[m].r>=q[i].r && m) m--;

		if (q[i].l>q[m].l && q[i].r>q[m].r) q[++m]=q[i];

	}

	for (int l=1,r=0,i=1;i<=n;i++) {

		while (r<m && q[r+1].l<=i && i<=q[r+1].r) r++;

		while (l<=m && q[l].r<i) l++;

		t[i]=(data){l,r};

	}

	f[0]=inv[0]=1;

	for (int x=1;x<=X;x++) {

		LL T=power(X,MOD-2)*(x-1)%MOD,P=(1-T+MOD)%MOD,B=power(P,MOD-2),K=1,S=1,sum=0;

		for (int i=1;i<=n;i++) inv[i]=inv[i-1]*B%MOD;

		for (int p=0,i=1;i<=n;i++,(K*=P)%=MOD) {

			for (;p<i && t[p].r<t[i].l-1;p++) (S+=MOD-inv[p]*f[p]%MOD)%=MOD;

			f[i]=S*K%MOD*T%MOD;

			(S+=f[i]*inv[i]%MOD)%=MOD;

		}

		K=1;

		for (int i=n;i>=1;i--,(K*=P)%=MOD) if (t[i].r==m) (sum+=f[i]*K%MOD)%=MOD;

		(ans+=(1-sum+MOD))%=MOD;

	}

	printf("%lld",ans);

	return 0;

}