#include<bits/stdc++.h>
// #pragma optimize("-O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,avx,mmx,tune=native")
// #define ll long long
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef long long ll;
#define vvi vector<vector<ll>>
#define vi vector<ll>
#define sz(a) ll((a).size())
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1)
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
// typedef tree<
// ll,
// null_type,
// less<ll>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;
#define int long long
const ll MOD =  998244353;
const ll BIG_INF = 4e18;
const ll INF = 1e9;
const ll mod =  998244353;
ll fast_exp(ll a, ll b)
{
    if(b <= 0)
       return 1;
    else
    {
       ll res = 1;
       res = fast_exp(a,b/2);
       res = res % mod;     
       res = (res*res)%mod;
       if(b%2 == 1)
          res = (res*a)%mod;
       return res;
 
    }
}





mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//shuffle(v.begin(),v.end(),rng);
 
ll true_rand(ll n) {
    // Returns a random number between 0 and n - 1 inclusive using mt19937.
    uniform_int_distribution<ll> uid(0, n - 1);
    return uid(rng);
}

// gambler's ruin: A has i, B has N-i  
// P[i] = A wins = (1 - (q/p)^i)/(1 - (q/p)^n) 
    


// ll fact[N] = {};
// ll fac_inv[N] = {};
// void precompute_factorial()
// {    
//     fact[0] = 1;
//     fac_inv[0] = 1;
//     for(ll i = 1; i < N; i++)
//     {
//         fact[i] = (fact[i-1] * i) % mod;
//         fac_inv[i] = (fast_exp(i,mod-2) * fac_inv[i-1]) % mod;
//     }
// }
// ll binom(ll n, ll r)
// {
//   if(r < 0 || r > n || n < 0)
//       return 0;
//   ll ans = fact[n];
//   ans = (ans * fac_inv[n-r]) % mod;
//   ans = (ans * fac_inv[r]) % mod;
//   return ans;
// }

const ll N = 1e5+1000;
typedef double ld;
const long double pi = acos(-1.0);
using cd = complex<double>;
const double PI = acos(-1);

int dp[102][102][5005] = {};

int32_t main()  
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("list_of_clgs_icpc.txt","r",stdin);
    int n;
    cin >> n;
    int w[n + 1] = {};
    int sum = 0;
    ll fac[200] = {};
    fac[0] = 1;
    for(int i = 1; i < 200; i++)
    {
      fac[i] = (i * fac[i-1]) % mod;
    }
    for(int i = 1; i <= n; i++)
    {  
      cin >> w[i];
      sum += w[i];
    }
    if(sum % 2 == 1)
    {
      cout << 0 << endl;
      return 0;
    }
   dp[0][0][0] = 1;
   int targ = sum / 2;
   for(int i = 1; i <= n; i++)
   {
       for(int j = 0; j < n; j++)
       {
         for(int s = 0; s <= targ; s++)
         {
            dp[i][j][s] += dp[i-1][j][s];
            if(dp[i][j][s] > mod)
               dp[i][j][s] -= mod;

            if(s + w[i] <= targ)
            {
               dp[i][j+1][s + w[i]] += dp[i-1][j][s];
               if(dp[i][j+1][s + w[i]] > mod)
                  dp[i][j + 1][s + w[i]] -= mod;
            }
         }
       }
   }

      ll ans = 0;
      for(int j = 1; j < n; j++)
      {
         ll ways = dp[n][j][targ];
         ways = (ways * fac[j]) % mod;
         ways = (ways * fac[n - j]) % mod;
         ans = (ans + ways) % mod;
      }

       cout << ans << endl;

   return 0;
    
}
    

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using ll = long long;
using ld = long double;



#define mp make_pair

const int p = 1e9 + 7;

int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}


mt19937 rnd(time(0));


const int N = 1000005;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    if (n<k) return 0;
    if (n<0 || k<0) return 0;
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}




/*struct DSU
{
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU (int n)
    {
        parent.resize(n);
        sz.resize(n);
        for (int i = 0; i<n; i++) make_set(i);
    }
};*/

int f(char c)
{
    if (c=='A') return 0; else return 1;
}

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

    int n;
    char caa, cab, cba, cbb;
    cin>>n>>caa>>cab>>cba>>cbb;

    int aa, ab, ba, bb;
    aa = f(caa); ab = f(cab); ba = f(cba); bb = f(cbb);

    vector<int> fin(n+1);
    fin[0] = 1;
    fin[1] = 1;
    for (int i = 2; i<=n; i++) fin[i] = add(fin[i-1], fin[i-2]);

    if (ab == 0)
    {
        if (aa==0) {cout<<1; return 0;}
        //now ab = 0, aa = 1
        if (ba==1)
        {
            cout<<po(2, n-3); return 0;
        }
        cout<<fin[n-2]; return 0;
        //now ba = 0
    }
    else
    {
        if (bb==1) {cout<<1; return 0;}
        //now ab = 1; bb = 0
        if (ba==0)
        {
            cout<<po(2, n-3); return 0;
        }
        cout<<fin[n-2]; return 0;
    }
}

/*
3 2
1 2 3
2 3 3
 */