#include using namespace std; #define i64 long long const int MOD=998244353; int addm(int a,int b){ a+=b; if(a>=MOD) a-=MOD; if(a<0) a+=MOD; return a; } int mulm(i64 a,i64 b){ return int((a*b)%MOD); } int pw(i64 a,i64 e){ i64 r=1%MOD; a%=MOD; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return int(r); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 n; int k; if(!(cin>>n>>k)) return 0; int m; cin>>m; vectorL(k+1,0); for(int i=0;i>l>>r; if(r>=1 && r<=k) L[r]=max(L[r],l); // 同右端点取最大的l } // 计数:在1..k中选t个位置,使每个限制区间都有至少一个被选位置 vector> dp(k+1,vector(k+1,0)); dp[0][0]=1; for(int i=1;i<=k;i++){ dp[i][0]=dp[i-1][0]; if(L[i]) dp[i][0]=addm(dp[i][0],-dp[L[i]-1][0]); for(int j=1;j<=i;j++){ int v=addm(dp[i-1][j],dp[i-1][j-1]); // 选/不选i if(L[i]) v=addm(v,-dp[L[i]-1][j]); // 保证[L[i],i]内至少选1个 dp[i][j]=v; } } vector cnt=dp[k]; // cnt[t]:满足限制的大小为t的子集个数 // 预处理C(t,s)与s^n vector fact(k+1,1),invf(k+1,1); for(int i=1;i<=k;i++) fact[i]=mulm(fact[i-1],i); invf[k]=pw(fact[k],MOD-2); for(int i=k;i>=1;i--) invf[i-1]=mulm(invf[i],i); auto C=[&](int n,int r)->int{ if(r<0||r>n) return 0; return mulm(fact[n],mulm(invf[r],invf[n-r])); }; vector p(k+1,0); for(int s=0;s<=k;s++) p[s]=pw(s,n); // surj[t] = t!S(n,t) = sum_{s=0..t} C(t,s)*(-1)^{t-s}*s^n vector surj(k+1,0); for(int t=0;t<=k;t++){ int v=0; for(int s=0;s<=t;s++){ int term=mulm(C(t,s),p[s]); if((t-s)&1) v=addm(v,-term); else v=addm(v,term); } surj[t]=v; } // 汇总答案:对每个t,选择的位置集合大小为t,然后把n个不同球映射到这t个已选盒子且每个非空 int lim=min(k,n); int ans=0; for(int t=0;t<=lim;t++) ans=addm(ans,mulm(cnt[t],surj[t])); cout<