// Problem: D - Cooking
// Contest: AtCoder - AtCoder Beginner Contest 204
// URL: https://atcoder.jp/contests/abc204/tasks/abc204_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long int
#define vl vector<ll>
#define pl pair<ll,ll>
#define pb push_back
#define F first
#define S second
using namespace std;

ll findMin(ll arr[], ll n)
{
    // Calculate sum of all elements
    ll sum = 0;
    for (ll i = 0; i < n; i++)
        sum += arr[i];
 
    // Create an array to store results of subproblems
    bool dp[n+1][sum+1];
 
    // Initialize first column as true. 0 sum is possible
    // with all elements.
    for (ll i = 0; i <= n; i++)
        dp[i][0] = true;
 
    // Initialize top row, except dp[0][0], as false. With
    // 0 elements, no other sum except 0 is possible
    for (ll i = 1; i <= sum; i++)
        dp[0][i] = false;
 
    // Fill the partition table in bottom up manner
    for (ll i=1; i<=n; i++)
    {
        for (ll j=1; j<=sum; j++)
        {
            // If i'th element is excluded
            dp[i][j] = dp[i-1][j];
 
            // If i'th element is included
            if (arr[i-1] <= j)
                dp[i][j] |= dp[i-1][j-arr[i-1]];
        }
    }
  
    // Initialize difference of two sums.
    ll diff = 10000000000;
     
    // Find the largest j such that dp[n][j]
    // is true where j loops from sum/2 t0 0
    for (ll j=sum/2; j>=0; j--)
    {
        // Find the
        if (dp[n][j] == true)
        {
            diff = sum-2*j;
            break;
        }
    }
    return diff;
}

int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        ll t,n,i,j,k,s=0,d;
        cin >> n;
        ll a[n];
        for(i=0;i<n;i++)
        {
        cin >> a[i];
        s+=a[i];
        }
        d=findMin(a,n);
        cout << (s+d)/2;
        
        return 0;
}
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

ll modinv(ll a, ll m)
{
    assert(m > 0);
    if (m == 1)
        return 0;
    a %= m;
    if (a < 0)
        a += m;
    assert(a != 0);
    if (a == 1)
        return 1;
    return m - modinv(m, a) * m / a;
}

template <int MOD_>
struct modnum
{
private:
    int v;

public:
    static const int MOD = MOD_;

    modnum() : v(0) {}
    modnum(ll v_) : v(int(v_ % MOD))
    {
        if (v < 0)
            v += MOD;
    }
    explicit operator int() const { return v; }
    friend bool operator==(const modnum &a, const modnum &b) { return a.v == b.v; }
    friend bool operator!=(const modnum &a, const modnum &b) { return a.v != b.v; }

    modnum operator~() const
    {
        modnum res;
        res.v = modinv(v, MOD);
        return res;
    }

    modnum &operator+=(const modnum &o)
    {
        v += o.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    modnum &operator-=(const modnum &o)
    {
        v -= o.v;
        if (v < 0)
            v += MOD;
        return *this;
    }
    modnum &operator*=(const modnum &o)
    {
        v = int(ll(v) * ll(o.v) % MOD);
        return *this;
    }
    modnum &operator/=(const modnum &o)
    {
        return *this *= (~o);
    }

    friend modnum operator+(const modnum &a, const modnum &b) { return modnum(a) += b; }
    friend modnum operator-(const modnum &a, const modnum &b) { return modnum(a) -= b; }
    friend modnum operator*(const modnum &a, const modnum &b) { return modnum(a) *= b; }
    friend modnum operator/(const modnum &a, const modnum &b) { return modnum(a) /= b; }
};

using num = modnum<998244353>;

vector<num> fact;
vector<num> ifact;

void init()
{
    fact = {1};
    for (int i = 1; i < 3005; i++)
        fact.push_back(i * fact[i - 1]);
    for (num x : fact)
        ifact.push_back(1 / x);
}

num ncr(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return fact[n] * ifact[k] * ifact[n - k];
}

num powmod(num x, int a)
{
    if (a == 0)
        return 1;
    if (a & 1)
        return x * powmod(x, a - 1);
    return powmod(x * x, a / 2);
}

const int N = 105;

num dp[N][N][50 * N];

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    cin >> n;

    init();

    vi a(n);
    fori(i, n) cin >> a[i];

    int sum = accumulate(all(a), 0);
    if (sum % 2)
    {
        cout << 0 << endl;
        return 0;
    }

    dp[0][0][0] = 1;
    fori(i, n)
    {
        fori(j, i + 1)
        {
            fori(k, min(50 * N, 100 * j + 1))
            {
                if (dp[i][j][k] == 0)
                    continue;
                dp[i + 1][j][k] += dp[i][j][k];
                if (k + a[i] < 50 * N)
                    dp[i + 1][j + 1][k + a[i]] += dp[i][j][k];
            }
        }
    }

    num ans = 0;
    sum >>= 1;
    fori(i, n + 1){
        ans += dp[n][i][sum] * fact[i] * fact[n - i];
    }

    cout << int(ans) << endl;

    time_taken();
    return 0;
}