我觉着这是$O(mk)$ 的啊QAQ

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
namespace lyt{
	const int N=100001;
	int n,m,k,x[N],y[N],top;
	unordered_map<int,int> qwq;
	long long int dp[N],dp2[N];
	long long int sum,p=998244353;
	void main(){
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=k;i++){
			scanf("%d%d",&x[i],&y[i]);
			if(qwq[y[i]]==0){
				qwq[y[i]]=top++;
			}
		}
		if(qwq[1]==0){
			qwq[1]=top++;
		}
		dp[qwq[1]]=1;
		sum=1;
		for(int i=1;i<=m;i++){
			dp2[top]=(sum-dp[top]+p)%p;
			dp2[qwq[1]]=(sum-dp[qwq[1]]+p)%p;
			for(int o=1;o<=k;o++){
				dp2[qwq[y[o]]]=sum-dp[qwq[y[o]]];
			}
			for(int o=1;o<=k;o++){
				if(x[o]==y[o]){
					continue;
				}
				if(qwq[x[o]]==0){
					dp2[qwq[y[o]]]-=dp[top];
				}
				else{
					dp2[qwq[y[o]]]-=dp[qwq[x[o]]];
				}
				dp2[qwq[y[o]]]=(dp2[qwq[y[o]]]+p)%p;
			}
			sum=0;
			for(int o=1;o<=k;o++){
				if(dp2[qwq[y[o]]]==-1){
					continue;
				}
				dp[qwq[y[o]]]=dp2[qwq[y[o]]];
				dp2[qwq[y[o]]]=-1;
				sum+=dp[qwq[y[o]]];
				sum%=p;
			}
			if(dp2[qwq[1]]!=-1){
				dp[qwq[1]]=dp2[qwq[1]];
				sum=(sum+dp[qwq[1]])%p;
			}
			dp[top]=dp2[top];
			sum=(sum+1LL*(n-top)*dp[top])%p;
		}
		printf("%lld\n",dp[qwq[1]]%p);
	}
}
int main(){
	lyt::main();
	return 0;
}