#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int maxn=1e5+10,mod=998244353; int n,m,k; int q_pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } pii a[maxn]; int cnt[maxn]; int ans; int power[maxn]; void dfs(int p) { if(p>n) { for(int i=1;i<=m;i++) ans=(ans+power[cnt[i]])%mod; // for(int i=1;i<=n;i++) cout<<a[i].fi<<" "<<a[i].se<<endl; // for(int i=1;i<=m;i++) cout<<cnt[i]<<" "; // cout<<endl<<endl; return ; } for(int i=1;i<=m;i++) { if(i<=a[p-1].fi) continue; for(int j=i;j<=m;j++) { if(j<=a[p-1].se) continue; for(int k=i;k<j;k++) cnt[k]++; a[p]=mp(i,j); dfs(p+1); for(int k=i;k<j;k++) cnt[k]--; } } } int f[60][60][60],g[60][60][60]; int pre[maxn]; signed main() { // freopen("segment.in","r",stdin); // freopen("segment.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=1e5;i++) power[i]=q_pow(i,k); if(n>m) { cout<<0<<endl; return 0; } if(m<=7) { dfs(1); cout<<ans<<endl; return 0; } if(n==1) { int ans=0; for(int i=1;i<m;i++) ans=(ans+i*(i+1)/2)%mod; cout<<ans<<endl; return 0; } if(m<=350&&n==2) { dfs(1); cout<<ans<<endl; return 0; } if(k==1&&m<=40) { memset(f,-0x3f,sizeof(f)); for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) f[1][i][j]=j-i,g[1][i][j]=1; for(int now=2;now<=n;now++) for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) { int t=0; for(int l=1;l<i;l++) for(int r=l;r<j;r++) if(g[now-1][l][r]!=0) t+=f[now-1][l][r]+(j-i)*g[now-1][l][r],g[now][i][j]+=g[now-1][l][r],g[now][i][j]%=mod; if(g[now][i][j]) f[now][i][j]=t%mod; } for(int i=1;i<=m;i++) { for(int j=i;j<=m;j++) if(f[n][i][j]>=0) ans+=f[n][i][j],ans%=mod; } cout<<ans%mod<<endl; return 0; } if(k==998244352&&m<=40) { memset(f,-0x3f,sizeof(f)); for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) f[1][i][j]=j-i,g[1][i][j]=1; for(int now=2;now<=n;now++) for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) { int t=0; for(int l=1;l<i;l++) for(int r=l;r<j;r++) if(g[now-1][l][r]!=0) t+=f[now-1][l][r]+min(j-r,j-i)*g[now-1][l][r],g[now][i][j]+=g[now-1][l][r],g[now][i][j]%=mod; if(g[now][i][j]) f[now][i][j]=t%mod; } // for(int i=1;i<=n;i++) // { // for(int l=1;l<=m;l++) // { // for(int r=l;r<=m;r++) cout<<f[i][l][r]<<" "; // cout<<endl; // } // cout<<endl; // } for(int i=1;i<=m;i++) { for(int j=i;j<=m;j++) if(f[n][i][j]>=0) ans+=f[n][i][j],ans%=mod; } cout<<ans%mod<<endl; return 0; } for(int i=1;i<=1e5;i++) pre[i]=pre[i-1]+i; int t=0; for(int i=1;i<=m;i++) t+=pre[i-1]; ans=t*t/2; for(int i=1;i<=m;i++) { ans-=pre[i-1]; } cout<<ans<<endl; return 0; }