#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
inline void mod(ll &x){
	if(x>=MOD)x-=MOD;
}
vector<ll> fact;
vector<ll> ifact;
ll add(ll a,ll b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
ll mult(ll a,ll b)
{
	return (a*1LL*b)%MOD;
}
ll binpow(ll a, ll b)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
ll choose(ll a, ll b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	ll r = mult(ifact[b],ifact[a-b]);
	r = mult(r,fact[a]);
	return r;
}
ll permute(ll a,ll b){
	ll res = mult(fact[a],ifact[a-b]);
	return res;
}
ll inv(int a){return binpow(a,MOD-2);}
void init(ll n)
{
	fact.clear(); ifact.clear();
	fact.resize(n+1);
	ifact.resize(n+1);
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=n;i++){fact[i]=mult(fact[i-1],i);}
	ifact[n] = inv(fact[n]);
	for(int i=n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
}
int main()
{
	owo
	int n;
	cin>>n;
	init(1000000);
	int sum = 0;
	vector<int>a(n);
	for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}
	if(sum%2){
		cout<<0;
		return 0;
	}
	sum/=2;
	VII dp(n+1,vector<ll>(sum+1));
	dp[0][0] = 1;
	for(int i=0;i<n;i++){
		for(int j=n;j>=1;j--){
			for(int k=a[i];k<=sum;k++){
				dp[j][k]+=dp[j-1][k-a[i]];
				mod(dp[j][k]);
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=n;i++){
		ll res = dp[i][sum]*fact[i]%MOD;
		res*=fact[n-i];
		res%=MOD;
		//cout<<res<<'\n';
		ans+=res;
		ans%=MOD;
	}
	//cout<<"TES"<<'\n';
	cout<<ans;
	
}

#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> bool chmin(T &a,T b) {if(a>b) {a=b; return true;} return false;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=1ll<<60;

ll rui(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1) ans=ans*a%mod;
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[1010];

int main(){
  dp[1]=2;
  dp[2]=3;
  rep1(i,1e3) dp[i+2]=dp[i+1]+dp[i];
  int n; cin >> n;
  char a,b,c,d; cin >> a >> b >> c >> d;
  if(n==2||n==3){
    cout << 1 << endl;
    return 0;
  }
  if(b=='B'){
    if(d=='B'){
      cout << 1 << endl;
    }
    else{
      if(c=='A'){
        cout << rui(2,n-3) << endl;
      }
      else{
        cout << dp[n-3] << endl;
      }
    }
  }
  else{
    if(a=='A'){
      cout << 1 << endl;
    }
    else{
      if(c=='B'){
        cout << rui(2,n-3) << endl;
      }
      else{
        cout << dp[n-3] << endl;
      }
    }
  }
  
}