/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second   
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define setval(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define trav(x , a) for(auto &x : a)
#define sz(a) ((int)a.size())
typedef long long ll ; 

#define int ll

using namespace std;

const int N = 3e5 +5 ;
const int mod = 998244353;
const ll inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

typedef pair<int, int> pii; 
typedef pair<int , pii> ipii ;
typedef pair<pii , int> piii ; 
typedef unsigned long long ull ;
typedef long double ld;

ll po(ll x,ll y,ll p = mod) {ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}


    // [x][i] => (M - x)^i
int M_minus_x[5001][5001];
int M_pow[5001];

void solve()
{
    int n  , m ;
    cin >> n >> m ;

    for(int x = 1 ;  x <= m ; ++x){
        int mul = m - x;
        int res = 1;
        for(int i = 0 ; i <= n ; ++i){
            M_minus_x[x][i] = res; 
            res = (1LL * res * mul) % mod;
        }
    }

    ll res = 1;
    for(int i = 0 ; i <= n ; ++i){
        M_pow[i] = res;
        res = (1LL * res * m) % mod;
    }

    int ans = (n * po(m , n)) % mod;
    rep(d , n){
        if(!d) continue;
        int cnt = n - d;
        ll res = (cnt * M_pow[n - 1 - d]) % mod;
        repA(x , 1 , m){
            int tmp = (1LL * res * M_minus_x[x][d - 1]) % mod;
            ans = (ans +  mod - tmp) % mod;
        }
    }
    cout << ans;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        cout << "\n" ;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int iv2=5e8+4;
const int lim=1000000;
const int jzm=1e6+7;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int n,a[MAXN],f[MAXN][2],ans;
signed main(){
	read(n);for(int i=1;i<=n;i++)read(a[i]);int sum=0;f[0][1]=1;
	for(int i=1;i<=n;i++)f[i][0]=f[i-1][1],f[i][1]=add(f[i-1][0],f[i-1][1]);
	for(int i=1;i<=n;i++){
		//printf("%d:%d %d\n",i,f[i][0],f[i][1]);
		ans=add(1ll*a[i]*f[i-1][1]%mo*add(f[n-i][0],f[n-i][1])%mo,ans);
		if(n-i>0)ans=add(1ll*(mo-a[i])*f[i-1][0]%mo*add(f[n-i-1][0],f[n-i-1][1])%mo,ans);
		else ans=add(1ll*(mo-a[i])*f[i-1][0]%mo,ans);
	}
	printf("%d\n",ans);
	return 0;
}
