#include "bits/stdc++.h"
using namespace std;
#define ll                long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
 
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
const int N = 2e5+2;
ll fact[N],ifact[N];

/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll inv(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, inv(b, m), m) + m) % m;} 
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;}
/*--------------------------------------------------------------------------------------------------------------------------*/

void add(ll &a, ll b){
    a = (a+b)%MM;
}

void comb(void){
    memset(fact,1,sizeof(fact));
    memset(ifact,1,sizeof(ifact));
    rep(i,2,N)fact[i]*=fact[i-1]*i;
    rep(i,2,N) ifact[i]*= mod_mul(ifact[i-1],inv(i,M),M);
}
void solve(){
    ll n;
    cin>>n;
    ll a[n];
    rep(i,0,n){
        char t;
        cin>>t;
        if(t=='+')cin>>a[i];
        else a[i]=-1;
    }
    ll ans=0;
    rep(x,0,n){
        if(a[x]!=-1){
            vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
            dp[0][0]=1;
            rep(i,0,n){
                rep(c,0,n){
                    add(dp[i+1][c], dp[i][c]);
                    if(i<x){
                        if(a[i]>=0){
                            if(a[i]<=a[x]){
                                add(dp[i+1][c+1], dp[i][c]);
                            }
                            else add(dp[i+1][c], dp[i][c]);
                        }
                        else{
                            if(c>0){
                                add(dp[i+1][c-1], dp[i][c]);
                            }else{
                                add(dp[i+1][c], dp[i][c]);
                            }
                        }
                    }
                    else if(i>x){
                        if(a[i]>=0){
                            if(a[i]<a[x]){
                                add(dp[i+1][c+1], dp[i][c]);
                            }
                            else add(dp[i+1][c], dp[i][c]);
                        }
                        else{
                            if(c>0){
                                add(dp[i+1][c-1], dp[i][c]);
                            }else{
                                ;
                            }
                        }
                    }
                }
            }
            rep(i,0,n+1){
                ans =(ans+ a[x]*(dp[n][i])%MM);
            }
        }
    }
    cout<<ans%MM<<endl;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
    #endif 
        solve();
	return 0;
}
### Prompt

Your task is to create a Cpp solution to the following problem:

You are given a sequence A, where its elements are either in the form + x or -, where x is an integer.

For such a sequence S where its elements are either in the form + x or -, define f(S) as follows:

  * iterate through S's elements from the first one to the last one, and maintain a multiset T as you iterate through it. 
  * for each element, if it's in the form + x, add x to T; otherwise, erase the smallest element from T (if T is empty, do nothing). 
  * after iterating through all S's elements, compute the sum of all elements in T. f(S) is defined as the sum. 



The sequence b is a subsequence of the sequence a if b can be derived from a by removing zero or more elements without changing the order of the remaining elements. For all A's subsequences B, compute the sum of f(B), modulo 998 244 353.

Input

The first line contains an integer n (1≤ n≤ 500) — the length of A.

Each of the next n lines begins with an operator + or -. If the operator is +, then it's followed by an integer x (1≤ x<998 244 353). The i-th line of those n lines describes the i-th element in A.

Output

Print one integer, which is the answer to the problem, modulo 998 244 353.

Examples

Input


4
-
+ 1
+ 2
-


Output


16

Input


15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-


Output


750759115

Note

In the first example, the following are all possible pairs of B and f(B):

  * B= {}, f(B)=0. 
  * B= {-}, f(B)=0. 
  * B= {+ 1, -}, f(B)=0. 
  * B= {-, + 1, -}, f(B)=0. 
  * B= {+ 2, -}, f(B)=0. 
  * B= {-, + 2, -}, f(B)=0. 
  * B= {-}, f(B)=0. 
  * B= {-, -}, f(B)=0. 
  * B= {+ 1, + 2}, f(B)=3. 
  * B= {+ 1, + 2, -}, f(B)=2. 
  * B= {-, + 1, + 2}, f(B)=3. 
  * B= {-, + 1, + 2, -}, f(B)=2. 
  * B= {-, + 1}, f(B)=1. 
  * B= {+ 1}, f(B)=1. 
  * B= {-, + 2}, f(B)=2. 
  * B= {+ 2}, f(B)=2. 



The sum of these values is 16.

### Response

```cpp
#include "bits/stdc++.h"
using namespace std;
#define ll                long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
 
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
const int N = 2e5+2;
ll fact[N],ifact[N];

/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll inv(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, inv(b, m), m) + m) % m;} 
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;}
/*--------------------------------------------------------------------------------------------------------------------------*/

void add(ll &a, ll b){
    a = (a+b)%MM;
}

void comb(void){
    memset(fact,1,sizeof(fact));
    memset(ifact,1,sizeof(ifact));
    rep(i,2,N)fact[i]*=fact[i-1]*i;
    rep(i,2,N) ifact[i]*= mod_mul(ifact[i-1],inv(i,M),M);
}
void solve(){
    ll n;
    cin>>n;
    ll a[n];
    rep(i,0,n){
        char t;
        cin>>t;
        if(t=='+')cin>>a[i];
        else a[i]=-1;
    }
    ll ans=0;
    rep(x,0,n){
        if(a[x]!=-1){
            vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
            dp[0][0]=1;
            rep(i,0,n){
                rep(c,0,n){
                    add(dp[i+1][c], dp[i][c]);
                    if(i<x){
                        if(a[i]>=0){
                            if(a[i]<=a[x]){
                                add(dp[i+1][c+1], dp[i][c]);
                            }
                            else add(dp[i+1][c], dp[i][c]);
                        }
                        else{
                            if(c>0){
                                add(dp[i+1][c-1], dp[i][c]);
                            }else{
                                add(dp[i+1][c], dp[i][c]);
                            }
                        }
                    }
                    else if(i>x){
                        if(a[i]>=0){
                            if(a[i]<a[x]){
                                add(dp[i+1][c+1], dp[i][c]);
                            }
                            else add(dp[i+1][c], dp[i][c]);
                        }
                        else{
                            if(c>0){
                                add(dp[i+1][c-1], dp[i][c]);
                            }else{
                                ;
                            }
                        }
                    }
                }
            }
            rep(i,0,n+1){
                ans =(ans+ a[x]*(dp[n][i])%MM);
            }
        }
    }
    cout<<ans%MM<<endl;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
    #endif 
        solve();
	return 0;
}
```