#include <bits/stdc++.h>
using namespace std;

template<const int &MOD>
struct _m_int {
  int val;

  _m_int(int64_t v = 0) {
    if(v < 0) v = v % MOD + MOD;
    if(v >= MOD) v %= MOD;
    val = v;
  }

  static int inv_mod(int a, int m = MOD) {
    // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
    int g = m, r = a, x = 0, y = 1;

    while(r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  // wont work if we use #define int int64_t
  explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }

  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return x % m;
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit unsigned int.
    unsigned x_high = x >> 32, x_low = (unsigned) x;
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }

  _m_int& operator*=(const _m_int &other) {
    val = fast_mod((uint64_t) val * other.val);
    return *this;
  }

  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }

  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }

  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }

  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }

  // wont work if we use #define int int64_t
  _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  _m_int operator--(int) { _m_int before = *this; --*this; return before; }

  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }

  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }

  _m_int inv() const {
    return inv_mod(val);
  }

  _m_int pow(int64_t p) const {
    if(p < 0)	return inv().pow(-p);
    _m_int a = *this, result = 1;
    while(p > 0) {
      if(p & 1)	result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }

  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

const int MOD = 998244353;
using mint = _m_int<MOD>;

#define int int64_t








signed main(){	
	int n;	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; ++i){
		char c; cin >> c;
		if(c == '-'){
			a[i] = -1;
		}else{
			int x; cin >> x;
			a[i] = x;
		}
	}
		
	mint ans = 0;
	
	for(int k = 1; k <= n; ++k){
		if(a[k] < 0) continue;
		
		int x = a[k];
		
		// dp[i][j] denotes no. of ways s.t. after i elements number of elements strictly less than x are j.
		mint dp[n+5][n+5];
		
		dp[0][0] = 1;
		
		for(int i = 1; i < k; ++i){
			if(a[i] < 0){
				for(int j = 0; j < n; ++j){
					dp[i][j] = dp[i-1][j];
					if(j == 0){
						dp[i][j] += dp[i-1][0] + dp[i-1][1];
					}else{
						dp[i][j] += dp[i-1][j+1]; 
					}
					
				}
			}else{
				for(int j = 0; j < n; ++j){
					if(a[i] > x){
						dp[i][j] = 2 * dp[i-1][j];
					}else{
						dp[i][j] = dp[i-1][j];
						if(j > 0) dp[i][j] += dp[i-1][j-1];
					}
					
				}
			}
		}
		
		for(int j = 0; j < n; ++j) dp[k][j] = dp[k-1][j];
		
		for(int i = k + 1; i <= n; ++i){
			if(a[i] < 0){
				for(int j = 0; j < n; ++j){
					dp[i][j] = dp[i-1][j];
					dp[i][j] += dp[i-1][j+1]; 
					
				}
			}else{
				for(int j = 0; j < n; ++j){
					if(a[i] >= x){
						dp[i][j] = 2 * dp[i-1][j];
					}else{
						dp[i][j] = dp[i-1][j];
						if(j > 0) dp[i][j] += dp[i-1][j-1];
					}
					
				}
			}
		}
		
		for(int i = 0; i < n; ++i) ans += mint(x) * dp[n][i];
	}
	
	cout << ans;
	
}


















### 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;

template<const int &MOD>
struct _m_int {
  int val;

  _m_int(int64_t v = 0) {
    if(v < 0) v = v % MOD + MOD;
    if(v >= MOD) v %= MOD;
    val = v;
  }

  static int inv_mod(int a, int m = MOD) {
    // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
    int g = m, r = a, x = 0, y = 1;

    while(r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  // wont work if we use #define int int64_t
  explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }

  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return x % m;
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit unsigned int.
    unsigned x_high = x >> 32, x_low = (unsigned) x;
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }

  _m_int& operator*=(const _m_int &other) {
    val = fast_mod((uint64_t) val * other.val);
    return *this;
  }

  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }

  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }

  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }

  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }

  // wont work if we use #define int int64_t
  _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  _m_int operator--(int) { _m_int before = *this; --*this; return before; }

  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }

  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }

  _m_int inv() const {
    return inv_mod(val);
  }

  _m_int pow(int64_t p) const {
    if(p < 0)	return inv().pow(-p);
    _m_int a = *this, result = 1;
    while(p > 0) {
      if(p & 1)	result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }

  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

const int MOD = 998244353;
using mint = _m_int<MOD>;

#define int int64_t








signed main(){	
	int n;	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; ++i){
		char c; cin >> c;
		if(c == '-'){
			a[i] = -1;
		}else{
			int x; cin >> x;
			a[i] = x;
		}
	}
		
	mint ans = 0;
	
	for(int k = 1; k <= n; ++k){
		if(a[k] < 0) continue;
		
		int x = a[k];
		
		// dp[i][j] denotes no. of ways s.t. after i elements number of elements strictly less than x are j.
		mint dp[n+5][n+5];
		
		dp[0][0] = 1;
		
		for(int i = 1; i < k; ++i){
			if(a[i] < 0){
				for(int j = 0; j < n; ++j){
					dp[i][j] = dp[i-1][j];
					if(j == 0){
						dp[i][j] += dp[i-1][0] + dp[i-1][1];
					}else{
						dp[i][j] += dp[i-1][j+1]; 
					}
					
				}
			}else{
				for(int j = 0; j < n; ++j){
					if(a[i] > x){
						dp[i][j] = 2 * dp[i-1][j];
					}else{
						dp[i][j] = dp[i-1][j];
						if(j > 0) dp[i][j] += dp[i-1][j-1];
					}
					
				}
			}
		}
		
		for(int j = 0; j < n; ++j) dp[k][j] = dp[k-1][j];
		
		for(int i = k + 1; i <= n; ++i){
			if(a[i] < 0){
				for(int j = 0; j < n; ++j){
					dp[i][j] = dp[i-1][j];
					dp[i][j] += dp[i-1][j+1]; 
					
				}
			}else{
				for(int j = 0; j < n; ++j){
					if(a[i] >= x){
						dp[i][j] = 2 * dp[i-1][j];
					}else{
						dp[i][j] = dp[i-1][j];
						if(j > 0) dp[i][j] += dp[i-1][j-1];
					}
					
				}
			}
		}
		
		for(int i = 0; i < n; ++i) ans += mint(x) * dp[n][i];
	}
	
	cout << ans;
	
}


















```