//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0);
#define trav(x,a) for (auto& x: a)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define case(t) cout << "Case #" << (t) << ": "
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 998244353;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
const ld eps = 1e-9;

template<class T> void read(T& x) { cin >> x; }
template<class X, class Y> void read(pair<X,Y>& a) { read(a.first), read(a.second); }
template<class T, size_t U> void read(array<T,U>& x) { for (int i = 0; i < U; i++) read(x[i]); }
template<class T> void read(vector<T>& x) { trav(y, x) read(y); }
template<class T, class... O> void read(T& x, O&... y) { read(x), read(y...); }

string to_string(const char& x) { return string(1,x); }
string to_string(const char*& x) { return (string)x; }
string to_string(const string& x) { return x; }
template<class T, class U> string to_string(const pair<T,U>& x) { return to_string(x.first) + " " + to_string(x.second); }
template<class T, size_t U> string to_string(const array<T,U>& x) { string ret = ""; for (int i = 0; i < U; i++) ret += (!i ? "" : " ") + to_string(x[i]); return ret; }
template<class T> string to_string(const vector<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; }
template<class T> string to_string(const set<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; }
void print() { cout << endl; }
template<class T> void pr(const T& x) { cout << to_string(x); }
template<class T, class... O> void print(const T& x, const O&... y) { pr(x); if (sizeof...(y)) pr(" "); print(y...); }

int inv[N], ifac[N], fac[N];

inline int add(int x, int y) { return x+y < mod ? x+y : x+y-mod; }
inline int sub(int x, int y) { return x-y >= 0 ? x-y : x-y+mod; }
inline int mul(int x, int y) { return x * 1ll * y % mod; }
template<class T, class... O> inline int add(T x, O... y) { return add(x, add(y...)); }
template<class T, class... O> inline int mul(T x, O... y) { return mul(x, mul(y...)); }
inline int norm(int x) { return x >= 0 ? (x < mod ? x : x-mod) : x+mod; }
inline int pw(int x, int y) {
  int r = 1;
  for (; y; x = mul(x, x), y /= 2)
    if (y & 1)
      r = mul(r, x);
  return r;
}
inline int inverse(int x) { return pw(x, mod-2); }
inline int ncr(int n, int k) {
  if (n < k || k < 0) return 0;
  if (n < N) return mul(fac[n], ifac[n-k], ifac[k]);
  int r = 1;
  for (int i = 1; i <= k; i++)
    r = mul(r, n-i+1, inv[i]);
  return r;
}

void precomputeInverse(int n) {
  inv[1] = ifac[0] = ifac[1] = fac[0] = fac[1] = 1;
  for (int i = 2; i < n; i++) {
    inv[i] = mod - mul(mod / i, inv[mod % i]);
    fac[i] = mul(fac[i-1], i);
    ifac[i] = mul(ifac[i-1], inv[i]);
  }
}

int dp[2][55][55 * 105];
int v[55];

int main() {
  FIO
  precomputeInverse(N);
  int n; read(n);
  vector<int> a(n); read(a);
  // int n = 100;
  // vector<int> a(n, 100);
  int ans = 0;
  int s = 0;
  for (int i: a) s += i;
  if (s & 1) {
    print(0);
    return 0;
  }
  s /= 2;
  dp[0][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= min(i, n / 2); j++) {
      for (int k = 0; k <= s; k++) {
        dp[i & 1][j][k] = dp[(i & 1)^1][j][k];
        if (j > 0 && k >= a[i-1])
          dp[i & 1][j][k] = add(dp[i & 1][j][k], dp[(i & 1)^1][j - 1][k - a[i-1]]);
      }
    }
  }
  for (int i = 1; i <= n / 2; i++)
    ans = add(ans, mul(1 + (2 * i != n), dp[n & 1][i][s], fac[i], fac[n-i]));
  print(ans);
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = (int)1e9+7;
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int>arr(n+1);
	for(int i = 1; i<=n; i++){
		cin >> arr[i];
	}
	vector<vector<int>>dp(n+1,vector<int>(n+1));// current ans as we iterate through
	dp[1][0] = 1;
	// dp[i][j] is ans of currently being in ith subarray with sum of j under modulus of i
	vector<int>inc(n+1);//actual index of j modulus i is inc[i]+j; so index j holds the value of index j-inc[i] 
	//each iteration you either slap the current number into a new subarray, or you continue current subarray
	for(int i = 2; i<=n; i++){
		
		for(int j = n-1; j>=1; j--){
			int realind = (j+0*arr[i]-inc[j])%j;realind+=j; realind%=j;
			int realind2 = (j+1-0*arr[i]-inc[j+1])%(j+1); realind2+=(j+1); realind2%=(j+1);
			dp[j+1][realind2]+=dp[j][realind];dp[j+1][realind2]%=mod;
		}
		for(int j = n; j>=1; j--){
			inc[j]+=arr[i]; inc[j]%=j;
		}
	}
	int ans = 0;
	for(int j = 1; j<=n; j++){
		for(int k = 0; k<j; k++){
			int idx = (j+k-inc[j])%j;
			if(k==0)ans+=dp[j][idx];
			ans%=mod;
			//cout << dp[j][idx] << " ";
		}
		//cout << "\n";
		}
	cout << ans << "\n";
	return 0;
}