#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define P pair<int,char>
#define Tp tuple<int,int,int>
using Graph = vector<vector<P>>;

int main(){
    int N; cin >> N;
    vector<ll> a; ll A;
    rep(i,N){
        cin >> A; a.push_back(A);
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    ll m = 998244353;
    ll ans = 0; ll k = 0; ll pr = 0; ll n;
    rep(i,N){
        n = a[i]; k = (k*2-pr+n+m)%m;
        ans += (n*k)%m; ans %= m; pr = n;
        //cout <<ans << endl;
    }
    cout << ans  << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define int long long
#define sz(x) ((int)(x).size())
#define fill(x, value) memset(x, value, sizeof(x))
#define debug(x) cout << #x << " ------> " << x << "\n"
typedef pair<int, int> PII;

const int N = 3e3 + 3;
int arr[N], n, mod = 1e9 + 7, dp[N][N], nxt[N][N];

int ways(int i, int cur) {
    if (i == n + 1) return true;
    int sum = 0, tot = 0, onetime = 0;
    if (dp[i][cur] != -1) return dp[i][cur];
    if(nxt[i][cur] != -1) {
        onetime = 1;
        tot += ways(nxt[i][cur] + 1, cur + 1);
        tot += ways(nxt[i][cur] + 1, cur);
        tot %= mod;
    }
    return dp[i][cur] = onetime * tot % mod;
}

int powr(int a, int n, int m) {
    int res = 1;
    while (n) {
        if (n % 2) res = res * a % m;
        a = a * a % m;
        n /= 2;
    }
    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) dp[i][j] = -1, nxt[i][j] = -1;
    }

    for(int i = 1; i <= n; i++){
        map<int, int> mp;
        int pf = 0;
        mp[0] = 0;
        for(int j = 1; j <= n; j++){
            pf += arr[j];
            pf %= i;
            if(mp.count(pf)) {
                nxt[mp[pf] + 1][i] = j;
            }
            mp[pf] = j;
        }
    }

    int ans = ways(1, 1) * powr(2, mod - 2, mod) % mod;
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve();
        // cout << solve() << '\n';
    }

    cerr << "\nTime: " << clock() << " ms";
}