#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 2005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
string s[2005];
int h,w;
ll dp[N][N][5];

bool valid(int i,int j)
{
    return i>=0&&i<h&&j>=0&&j<w&&s[i][j]=='.';
}

ll run(int i,int j,int c)
{
    if(i==h-1&&j==w-1)
    {
        return 1;
    }
    if(dp[i][j][c]!=-1)
        return dp[i][j][c];
    ll ans=0;
    if(c==0)
    {
        if(valid(i,j+1)) ans=(ans+run(i,j+1,1));
        if(valid(i+1,j)) ans=(ans+run(i+1,j,2));
        if(valid(i+1,j+1)) ans=(ans+run(i+1,j+1,3));
    }
    else if(c==1)
    {
        ans=(ans+run(i,j,0));
        if(valid(i,j+1)) ans=(ans+run(i,j+1,1));
    }
    else if(c==2)
    {
        ans=(ans+run(i,j,0));
        if(valid(i+1,j)) ans=(ans+run(i+1,j,2));
    }
    else if(c==3)
    {
        ans=(ans+run(i,j,0));
        if(valid(i+1,j+1)) ans=(ans+run(i+1,j+1,3));
    }
    ans%=M;
    return dp[i][j][c]=ans;
}

main()
{
    memset(dp,-1,sizeof dp);
    cin>>h>>w;
    for(int i=0;i<h;i++)
        cin>>s[i];
    cout<<run(0,0,0);
}

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<deque>
#include<cstring>
#define ll long long
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pf push_front
#define MOD (ll)(998244353)
#define INF (ll)(1e9)
#define M 5000005
#define AC ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

template<class T> using PQ=priority_queue<T,vector<T>,greater<T> >;

ll fpow(ll x,ll y){
    ll r=1;
    while(y){
        if(y&1){
            r*=x;
            r%=MOD;
        }
        x=x*x%MOD;
        y>>=1;
    }
    return r;
}

ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    return y?gcd(y,x%y):x;
}
ll dp[105][10005],s[105];
signed main(){
    AC;
    s[0]=1;
    FOR(i,1,101) s[i]=(s[i-1]*i)%MOD;
    int n,w[105],sum=0;
    cin>>n;
    FOR(i,1,n+1){
        cin>>w[i];
        sum+=w[i];
    }
    if(sum&1) {
        cout<<0<<endl;
        return 0;
    }
    sum/=2;
    dp[0][0]=1;
    FOR(i,1,n+1)for(int j=i;j>0;j--)for(int k=sum;k>=w[i];k--) dp[j][k]=(dp[j][k]+dp[j-1][k-w[i]])%MOD;
    ll ans=0;
    FOR(i,1,n){
        ll tmp=s[i]*s[n-i]%MOD;
        tmp*=dp[i][sum];
        tmp%=MOD;
        ans=(ans+tmp)%MOD;
    }
    cout<<ans<<endl;
}
