#include <iostream>

using namespace std;
typedef long long ll;
ll dp[110][110][5010],mod = 998244353,w[110],f[110];
int main(){
    int i,j,k,n; cin >> n;
    ll sum = 0;
    for(i=0;i<n;i++){
        cin >> w[i]; sum += w[i];
    }
    if(sum&1){
        cout << 0 << endl;
        return 0;
    }
    dp[0][0][0] = 1;
    for(i=1;i<=n;i++){
        for(j=0;j<=n;j++){
            for(k=0;k<=sum/2;k++){
                (dp[i][j][k] += dp[i - 1][j][k]) %= mod;
                if(j>=1 && k + w[i - 1]<=sum/2) (dp[i][j][k + w[i - 1]] += dp[i - 1][j - 1][k]) %= mod;
            }
        }
    }
    ll ans = 0;
    f[0] = 1;
    for(i=1;i<=n;i++) f[i] = f[i - 1]*(ll)i%mod;
    for(j=0;j<=n;j++){
        (ans += dp[n][j][sum/2]*f[j]%mod*f[n - j]%mod) %= mod;
    }
    cout << ans << endl;
}
#include "bits/stdc++.h"
#include <chrono>
#include <random>
#define lli long long int
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 1000000000
#define common cout << "Case #" << w+1 << ": "  
#define maxn 200010

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

template< typename T> 
void PVecPrint(vector<T>&v) 
{ 
    for(int i=0;i<(int)v.size();i++) 
        cout << v[i].first << "," << v[i].second << ' '; 
    cout << '\n'; 
}
template<class T> 
void VecPrint(vector<T>&v)
{
    for(int i=0;i<v.size();i++) 
        cout << v[i] << ' ';
    cout << '\n';
}
/*-------------------------------------------------------------------Code-----------------------------------------------------------------*/

int dp[101][100001];

int main()
{
    int n;
    cin >> n;
    vector<int>v(n);
    int tot=0;
    for(int i=0;i<n;i++)
    {
        cin >> v[i];
        tot+=v[i];
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<100001;j++)
            dp[i][j]=0;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=100000;j++)
        {
            if(j==0)
            {
                dp[i][j]=1;
                continue;
            }
            if(v[i-1]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j] | dp[i-1][j-v[i-1]];
        }
    }
    int ans=INF;
    for(int i=0;i<=100000;i++)
    {
        if(dp[n][i])
            ans=min(ans,max(i,tot-i));
    }
    cout << ans << '\n';
}