#pragma region
#include <bits/stdc++.h>
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define prec fixed<<setprecision(9)
#define all(x) x.begin(),x.end()
using ll = long long;
using namespace std;
int mod = 998244353;

string to_string(string& s) {return '"'+s+'"';}
string to_string(bool& b) {return b?"true":"false";}
string to_string(const char* s) {string t; return to_string(t=s);}
template <class A, class B> string to_string(pair<A, B>& p) {return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template <class A> string to_string(A& v) {string s; for (auto &x : v) s+=(s.empty()?"":", ")+to_string(x); return "{"+s+"}";}
template<class... Ts> void _debug(Ts&... args){(..., (cerr<<" "<<to_string(args))); cerr<<endl;}
#ifdef apurv
#define debug(args...) cerr<<__LINE__<<" ["<<#args<<"]:", _debug(args)
#else
#define debug(...) 42
#endif
#pragma endregion

vector<int> arr;
int n;
vector<vector<int>> dp;
vector<int> fact;

// https://codeforces.com/contest/1536/submission/118638158
ll mod_add(ll a, ll b, ll m = mod) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m = mod) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}

int main()
{
    fastIO
    cin >> n;
    arr = vector<int>(n); for(auto&i : arr) cin >> i;
    if (accumulate(all(arr), 0) % 2) {
        cout << 0 << endl; return 0;
    }
    int h = accumulate(all(arr), 0) / 2;
    vector<int> fact(n + 5); fact[0] = 1;
    ll v = 1; 
    for (int i = 1; i < n+5; i++) {
        v *= i;
        if (v >= mod) v %= mod;
        fact[i] = v;
    }
    // debug(fact);
    ll ans = 0;
    vector<vector<ll>> dp(n + 1, vector<ll>(2*h + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int ln = n; ln >= 1; ln--)   
        {
            for (int s = 1; s <= h; s++)
             {
                if (arr[i] == s) {
                    if (ln != 1) continue;
                    dp[1][s] = mod_add(dp[1][s], 1);
                    debug(i, "1", s, "1");
                    if (i == 0 and s == h) {
                        ll v = fact[1];
                        v = mod_mul(v, fact[n - 1]);
                        v = mod_mul(v, 2);
                        ans = mod_add(ans, v);
                    }
                    continue;
                } else if (arr[i] > s) {
                    continue;
                }
                ll kitne = dp[ln - 1][s - arr[i]];
                if(kitne) debug(i, ln, s, kitne);
                dp[ln][s] = mod_add(dp[ln][s], kitne);
                if (i == 0 and ln != n and s == h) {
                    // debug(ln, kitne);
                    ll v = fact[ln];
                    v = mod_mul(v, fact[n - ln]);
                    v = mod_mul(v, 2);
                    v = mod_mul(v, kitne);
                    ans = mod_add(ans, v);
                }
            }
        }
    }
    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
#define repeq(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
#define rrep(i,a,b) for(int i=(int)(b)-1; i>=(int)(a); --i)
#define rrepeq(i,a,b) for(int i=(int)(b); i>=(int)(a); --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
// const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
string interval[2] = {" ", "\n"}; // {" ", "\n"}

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
template<> struct is_plural<string> : true_type{};

template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << " " << p.second; }
template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for(auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { if(vec.empty()) return os; bool pl = is_plural<T>(); os << vec.front(); for(auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[pl] << *itr; return os; }

bool CoutYN(bool a, string y = "Yes", string n = "No") { cout << (a ? y : n) << "\n"; return a; }

template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

long long modpow(int a, long long n, int mod = MOD) { long long ret = 1; do { if(n & 1) ret = ret * a % mod; a = 1LL * a * a % mod; } while(n >>= 1); return ret; }

template<typename T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<typename T> T LCM(T a, T b) { return a / GCD(a, b) * b; }

template<typename T1, typename T2> bool CompareBySecond(pair<T1, T2> a, pair<T1, T2> b) { return a.second != b.second ? a.second < b.second : a.first < b.first; }
template<typename T1, typename T2> bool CompareByInverse(pair<T1, T2> a, pair<T1, T2> b) { return a.first != b.first ? a.first < b.first : a.second > b.second; }


/* -------- <templates end> -------- */


void solve() {
  int n; cin >> n;
  vector<string> ans(1<<n);
  ans[1] = "AB";

  auto expand = [&](int i) -> void {
    string ret;
    for(auto &c : ans[i]) {
      rep(_,0,2) ret.push_back(c);
    }
    ans[i] = ret;
  };

  rep(i,1,n) {
    int from = 1<<(i-1);
    int to = 1<<i;
    ans[to] = ans[from] + ans[from];
    rep(j,1,to) {
      ans[to + j] = ans[to];
      rep(k,0,to) {
        if(ans[j][k] == 'B') {
          swap(ans[to + j][2*k], ans[to + j][2*k + 1]);
        }
      }
      expand(j);
    }
  }

  cout << ans.size() - 1 << '\n';
  rep(i,1,1<<n) cout << ans[i] << '\n';
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}
