In fact, the sought expected value can be represented as:

• \(\displaystyle \sum^{N}_{i=1} A_i \times \) (the probability that \(A_i\) yen is payed in the procedure).

Now let us find the probability \(p_i\) that \(A_i\) yen is payed during the procedure.

For convenience, let \(p_0=1\).
Then we have \(\displaystyle p_i = \frac{1}{N} \sum_{j=0}^{i-1} p_j\).
Why? The term \(\frac{1}{N} p_j\) represents the probability that the die shows \(i\) when \(x=j\) and he receives \(A_i\) yen.

This can be evaluated in a total of \(O(N)\) time using cumulative sums.
Here, dividing by \(N\) modulo \(998244353\) is achieved by multiplying by the modular inverse of \(N\). Reference (Japanese)

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353
#define FACSIZE 1048576

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

int main(){
  long long n;
  cin >> n;
  long long invn=modular_inverse(n);
  long long p=invn,res=0;
  for(long long i=0;i<n;i++){
    long long a;
    cin >> a;
    res+=p*a;res%=mod;
    p+=p*invn;p%=mod;
  }
  cout << res << "\n";
  return 0;
}