#include <bits/stdc++.h>
using namespace std;
#define ll      long long
#define ld      long double
#define ln      "\n"
#define pb      push_back
#define pll     pair<ll , ll>
#define ppll    pair<ll , pll>
#define vll     vector<ll>
#define vs      vector<string>
#define vpll    vector<pll>
#define vvll    vector<vector<ll>>
#define vvpll   vector<vpll>
#define f       first
#define s       second
#define bs      binary_search
#define lb      lower_bound
#define ub      upper_bound
#define sz(x)   (ll)x.size()
#define ppc     __builtin_popcount
#define ppcll   __builtin_popcountll
#define Test    ll T ; cin>>T ; for(ll tc = 1 ; tc <= T ; tc++)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL)
#define all(x)  x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pi      3.14159265358979323846
#define MAXX    LLONG_MAX
#define deb(x)  cerr<<#x<<" = "<<x<<ln;
const int MAX = INT_MAX , MAXN = 1e6 + 1;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;

template <typename T> istream& operator >> (istream &in , vector<T> &v) { for(auto &i: v) cin>>i; return in; }
template <typename T1 , typename T2> istream& operator >> (istream &in , pair<T1 , T2> &p) { cin>>p.f>>p.s; return in; }
template <typename T> ostream& operator << (ostream &out , vector<T> &v) { for(auto &i: v) cout<<i<<" "; return out; }
template <typename T1 , typename T2> ostream& operator << (ostream &out , pair<T1 , T2> &p) { cout<<p.f<<" "<<p.s<<" "; return out; }

void solve() {
    ll n , i , j , k , ans = 0;
    cin>>n;
    vector<char> op(n + 1);
    vll x(n + 1);
    for(i = 1 ; i <= n ; i++) {
        cin>>op[i];
        if(op[i] == '+') cin>>x[i];
    }
    for(i = 1 ; i <= n ; i++) {
        if(op[i] == '+') {
            vvll dp(n + 1 , vll(n + 2)); // dp[j][k] -> number of subsequences in 1....j (in which x[i] is present), number of items (less than or equals to x[i]) becomes k at the end of all operation of that subsequence
            dp[0][0] = 1;
            for(j = 1 ; j <= n ; j++) {
                for(k = 0 ; k <= n ; k++) {
                    // Taking jth element in the subsequence
                    if(op[j] == '-') {
                        dp[j][k] = (dp[j][k] + dp[j - 1][k + 1]) % MOD; // '-' will remove one element smaller than x[i], so in range 1....(j - 1) , smaller element equal to (k + 1)
                        if(k == 0 && j < i) dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD; // if '-' is encountered but j < i, then it doesn't matter if there is any smaller element or not
                    }
                    else {
                        if((x[j] < x[i]) || (j < i && x[j] == x[i])) { // if x[j] == x[i], then consider it smaller than x[i], if it is present before x[i] in the array
                            if(k > 0) dp[j][k] = (dp[j][k] + dp[j - 1][k - 1]) % MOD; // if smaller item is encountered and number of smaller items has become k, then number of smaller items in 1.....(j - 1) must be (k - 1) 
                        }
                        else dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD; // no change in the number of smaller items
                    }
                    // Not taking jth element in subsequence
                    if(j != i) dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD;
                }
            }
            for(j = 0 ; j <= n ; j++)  ans = (ans + (dp[n][j] * x[i]) % MOD) % MOD; // summation of number of subsequence containing x[i], such that smaller elements become j
        }
    }
    cout<<ans<<ln;
}
int32_t main() {
    fast_io;
    #ifndef ONLINE_JUDGE
        freopen("input.txt" , "r" , stdin);
        freopen("output.txt" , "w" , stdout);
    #endif

    // Test
    solve();

    return 0;
}
/*
    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.      [0]     (1)
    B= {+ 1, + 2, -}, f(B)=2.       (0) 
    B= {-, + 1, + 2}, f(B)=3.   [0]     (1)
    B= {-, + 1, + 2, -}, f(B)=2.    (0)
    B= {-, + 1}, f(B)=1.        [0]
    B= {+ 1}, f(B)=1.           [0]
    B= {-, + 2}, f(B)=2.            (0)
    B= {+ 2}, f(B)=2.               (0)
*/
### Prompt

Generate 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 ld      long double
#define ln      "\n"
#define pb      push_back
#define pll     pair<ll , ll>
#define ppll    pair<ll , pll>
#define vll     vector<ll>
#define vs      vector<string>
#define vpll    vector<pll>
#define vvll    vector<vector<ll>>
#define vvpll   vector<vpll>
#define f       first
#define s       second
#define bs      binary_search
#define lb      lower_bound
#define ub      upper_bound
#define sz(x)   (ll)x.size()
#define ppc     __builtin_popcount
#define ppcll   __builtin_popcountll
#define Test    ll T ; cin>>T ; for(ll tc = 1 ; tc <= T ; tc++)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL)
#define all(x)  x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pi      3.14159265358979323846
#define MAXX    LLONG_MAX
#define deb(x)  cerr<<#x<<" = "<<x<<ln;
const int MAX = INT_MAX , MAXN = 1e6 + 1;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;

template <typename T> istream& operator >> (istream &in , vector<T> &v) { for(auto &i: v) cin>>i; return in; }
template <typename T1 , typename T2> istream& operator >> (istream &in , pair<T1 , T2> &p) { cin>>p.f>>p.s; return in; }
template <typename T> ostream& operator << (ostream &out , vector<T> &v) { for(auto &i: v) cout<<i<<" "; return out; }
template <typename T1 , typename T2> ostream& operator << (ostream &out , pair<T1 , T2> &p) { cout<<p.f<<" "<<p.s<<" "; return out; }

void solve() {
    ll n , i , j , k , ans = 0;
    cin>>n;
    vector<char> op(n + 1);
    vll x(n + 1);
    for(i = 1 ; i <= n ; i++) {
        cin>>op[i];
        if(op[i] == '+') cin>>x[i];
    }
    for(i = 1 ; i <= n ; i++) {
        if(op[i] == '+') {
            vvll dp(n + 1 , vll(n + 2)); // dp[j][k] -> number of subsequences in 1....j (in which x[i] is present), number of items (less than or equals to x[i]) becomes k at the end of all operation of that subsequence
            dp[0][0] = 1;
            for(j = 1 ; j <= n ; j++) {
                for(k = 0 ; k <= n ; k++) {
                    // Taking jth element in the subsequence
                    if(op[j] == '-') {
                        dp[j][k] = (dp[j][k] + dp[j - 1][k + 1]) % MOD; // '-' will remove one element smaller than x[i], so in range 1....(j - 1) , smaller element equal to (k + 1)
                        if(k == 0 && j < i) dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD; // if '-' is encountered but j < i, then it doesn't matter if there is any smaller element or not
                    }
                    else {
                        if((x[j] < x[i]) || (j < i && x[j] == x[i])) { // if x[j] == x[i], then consider it smaller than x[i], if it is present before x[i] in the array
                            if(k > 0) dp[j][k] = (dp[j][k] + dp[j - 1][k - 1]) % MOD; // if smaller item is encountered and number of smaller items has become k, then number of smaller items in 1.....(j - 1) must be (k - 1) 
                        }
                        else dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD; // no change in the number of smaller items
                    }
                    // Not taking jth element in subsequence
                    if(j != i) dp[j][k] = (dp[j][k] + dp[j - 1][k]) % MOD;
                }
            }
            for(j = 0 ; j <= n ; j++)  ans = (ans + (dp[n][j] * x[i]) % MOD) % MOD; // summation of number of subsequence containing x[i], such that smaller elements become j
        }
    }
    cout<<ans<<ln;
}
int32_t main() {
    fast_io;
    #ifndef ONLINE_JUDGE
        freopen("input.txt" , "r" , stdin);
        freopen("output.txt" , "w" , stdout);
    #endif

    // Test
    solve();

    return 0;
}
/*
    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.      [0]     (1)
    B= {+ 1, + 2, -}, f(B)=2.       (0) 
    B= {-, + 1, + 2}, f(B)=3.   [0]     (1)
    B= {-, + 1, + 2, -}, f(B)=2.    (0)
    B= {-, + 1}, f(B)=1.        [0]
    B= {+ 1}, f(B)=1.           [0]
    B= {-, + 2}, f(B)=2.            (0)
    B= {+ 2}, f(B)=2.               (0)
*/
```