#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll mod=998244353;
ll N,M;
ll sum[5005];
ll POW[5005];
ll POWM[5005];
void init(){
for(ll i=0;i<5005;i++)POW[i]=1;
  for(ll i=0;i<5005;i++){
    ll x=0;
    for(ll j=0;j<M;j++){
    x=(x+POW[j])%mod;POW[j]=(j*POW[j])%mod;
    }sum[i]=x;
  }
POWM[0]=1;for(ll i=0;i<5005;i++)POWM[i+1]=(M*POWM[i])%mod;
}
int main(){
  cin>>N>>M;init();
  ll ans=N*POWM[N];
  for(ll n1=1;n1<N;n1++)
    for(ll n2=n1+1;n2<=N;n2++)
      ans=(ans+mod-(POWM[N-n2+n1-1]*sum[n2-n1-1])%mod)%mod;
  cout<<ans<<endl;
  return 0;
}
#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<queue>
#include<vector>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define mod 998244353
using namespace std;
inline int read(){
	int f=1,ans=0; char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return f*ans;
}
const int MAXN=111;
int f[2][MAXN][MAXN*MAXN],N,fac[MAXN],ifac[MAXN],inv[MAXN],A[MAXN],sum;
int binom(int a,int b){return fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
signed main(){
	//freopen("9.in","r",stdin);
	N=read(); for(int i=1;i<=N;i++) A[i]=read();
	fac[0]=fac[1]=inv[1]=ifac[0]=ifac[1]=1; for(int i=2;i<MAXN;i++) fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
	int cur=0; f[0][0][0]=1;
	for(int i=1;i<=N;i++){
		cur^=1; memset(f[cur],0,sizeof(f[cur]));
		for(int j=0;j<i;j++) for(int k=0;k<=sum;k++) f[cur][j][k]=f[cur^1][j][k];
		for(int j=0;j<i;j++) for(int k=0;k<=sum;k++) if(f[cur^1][j][k]) f[cur][j+1][k+A[i]]+=f[cur^1][j][k],f[cur][j+1][k+A[i]]%=mod;
		sum+=A[i];
	}
	if(sum&1){printf("0\n");return 0;}
	int Ans=0;
	for(int i=1;i<=N;i++) Ans+=f[cur][i][sum/2]*fac[i]%mod*fac[N-i]%mod,Ans%=mod;
	printf("%lld\n",Ans); return 0;
}