#include "bits/stdc++.h"
using namespace std;
namespace modular {
  template <typename> struct is_modular: std::false_type {};
  template <int M>
  struct static_mint {
    static_assert(0 < M, "Module must be positive");
    using mint = static_mint;
    int val;
    static_mint(): val() {}
    static_mint(long long x): val(x % M) { if (val < 0) val += M; }
    mint pow(long long n) const {
      mint ans = 1, x( * this);
      while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n /= 2;
      }
      return ans;
    }
    mint inv() const {
      return pow(M - 2);
    }
    friend mint pow(const mint & m, long long n) {
      return m.pow(n);
    }
    friend mint inv(const mint & m) {
      return m.inv();
    }
    mint operator + () const {
      mint m;
      m.val = val;
      return m;
    }
    mint operator - () const {
      mint m;
      m.val = M - val;
      return m;
    }
    mint & operator += (const mint & m) {
      if ((val += m.val) >= M) val -= M;
      return *this;
    }
    mint & operator -= (const mint & m) {
      if ((val -= m.val) < 0) val += M;
      return *this;
    }
    mint & operator *= (const mint & m) {
      val = (long long) val * m.val % M;
      return *this;
    }
    mint & operator /= (const mint & m) {
      val = (long long) val * m.inv().val % M;
      return *this;
    }
    friend mint operator + (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) += rhs;
    }
    friend mint operator - (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) -= rhs;
    }
    friend mint operator * (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) *= rhs;
    }
    friend mint operator / (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) /= rhs;
    }
    friend bool operator == (const mint & lhs,
      const mint & rhs) {
      return lhs.val == rhs.val;
    }
    friend bool operator != (const mint & lhs,
      const mint & rhs) {
      return lhs.val != rhs.val;
    }
    mint & operator++() {
      return *this += 1;
    }
    mint & operator--() {
      return *this -= 1;
    }
    mint operator++(int) {
      mint result( * this);* this += 1;
      return result;
    }
    mint operator--(int) {
      mint result( * this);* this -= 1;
      return result;
    }
    template <typename T> explicit operator T() const {
      return T(val);
    }
    friend std::ostream & operator << (std::ostream & os,
      const mint & m) {
      return os << m.val;
    }
    friend std::istream & operator >> (std::istream & is, mint & m) {
      long long x;
      is >> x;
      m = x;
      return is;
    }
  };
  template <int M> struct is_modular < static_mint <M>>: std::true_type {};
  template <int& _M> struct dynamic_mint {
    static constexpr int& M = _M;
    using mint = dynamic_mint;
    int val;
    dynamic_mint(): val() {}
    dynamic_mint(long long x): val(x % M) {
      if (val < 0) {
        val += M;
      }
    }
    mint pow(long long n) const {
      mint ans = 1, x( * this);
      while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n /= 2;
      }
      return ans;
    }
    mint inv() const {
      return pow(M - 2);
    }
    friend mint pow(const mint & m, long long n) {
      return m.pow(n);
    }
    friend mint inv(const mint & m) {
      return m.inv();
    }
    mint operator + () const {
      mint m;
      m.val = val;
      return m;
    }
    mint operator - () const {
      mint m;
      m.val = M - val;
      return m;
    }
    mint & operator += (const mint & m) {
      if ((val += m.val) >= M) val -= M;
      return *this;
    }
    mint & operator -= (const mint & m) {
      if ((val -= m.val) < 0) val += M;
      return *this;
    }
    mint & operator *= (const mint & m) {
      val = (long long) val * m.val % M;
      return *this;
    }
    mint & operator /= (const mint & m) {
      val = (long long) val * m.inv().val % M;
      return *this;
    }
    friend mint operator + (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) += rhs;
    }
    friend mint operator - (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) -= rhs;
    }
    friend mint operator * (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) *= rhs;
    }
    friend mint operator / (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) /= rhs;
    }
    friend bool operator == (const mint & lhs,
      const mint & rhs) {
      return lhs.val == rhs.val;
    }
    friend bool operator != (const mint & lhs,
      const mint & rhs) {
      return lhs.val != rhs.val;
    }
    mint & operator++() {
      return *this += 1;
    }
    mint & operator--() {
      return *this -= 1;
    }
    mint operator++(int) {
      mint result( * this);* this += 1;
      return result;
    }
    mint operator--(int) {
      mint result( * this);* this -= 1;
      return result;
    }
    template <typename T> explicit operator T() const {
      return T(val);
    }
    friend std::ostream & operator << (std::ostream & os,
      const mint & m) {
      return os << m.val;
    }
    friend std::istream & operator >> (std::istream & is, mint & m) {
      long long x;
      is >> x;
      m = x;
      return is;
    }
  };
};
using im = modular::static_mint<998244353>;
constexpr int N = 503;
int n;
int a[N];
im dp1[2][N];
im dp2[2][N];
// dp1 = ways to get to i with j to cover
int b[N];
im p2[N];
im solve_case(int k) {
  for (int i = 1; i <= n; i ++) {
    if (a[i] == -1)
      b[i] = -1;
    else {
      if (a[i] < a[k] || (a[i] == a[k] && i < k))
        b[i] = 1;
      else
        b[i] = 0;
    }
  }
  for (int i = 0; i < 2; i ++)
    for (int j = 0; j <= n; j ++) {
      dp1[i][j] = 0;
      dp2[i][j] = 0;
    }
  dp1[0][0] = 1;
  int cur = 0, nxt = 1;
  for (int i = 0; i + 1 < k; i ++) {
    for (int j = 0; j <= n; j ++) {
      // dont take
      dp1[nxt][j] += dp1[cur][j];
      // take
      if (b[i + 1] == -1)
        dp1[nxt][max(0, j + b[i + 1])] += dp1[cur][j];
      else if (j + b[i + 1] <= n)
        dp1[nxt][j + b[i + 1]] += dp1[cur][j];
      dp1[cur][j] = 0;
    }
    swap(cur, nxt);
  }
  if (k == n) {
    return p2[k - 1];
  }
  for (int i = 0; i < n; i ++)
    dp2[cur][i + 1] = dp1[cur][i];
  for (int i = k; i < n; i ++) {
    for (int j = 1; j <= n; j ++) {
      // only those alive matters
      // skip then
      dp2[nxt][j] += dp2[cur][j];
      // take
      if (b[i + 1] == -1)
        dp2[nxt][j - 1] += dp2[cur][j];
      else {
        if (j + b[i + 1] <= n)
          dp2[nxt][j + b[i + 1]] += dp2[cur][j];
      }
      dp2[cur][j] = 0;
    }
    swap(cur, nxt);
  }
  im res = 0;
  for (int i = 1; i <= n; i ++)
    res += dp2[cur][i];
  return res;
}
void solution() {
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    string s;
    cin >> s;
    if (s[0] == '-') a[i] = -1;
    else {
      cin >> a[i];
    }
  }
  im ans = 0;
  for (int i = 1; i <= n; i ++)
    if (a[i] != -1)
      ans += solve_case(i) * a[i];
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); int tc = 1;
#ifdef DEBUG
  freopen("input.txt", "r", stdin); 
#endif
  p2[0] = 1;
  for (int i = 1; i < N; i ++) p2[i] = p2[i - 1] * 2;
  // cin >> tc; 
  while (tc --) { solution(); cout << "\n"; }
}
### Prompt

Develop a solution in cpp to the problem described below:

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;
namespace modular {
  template <typename> struct is_modular: std::false_type {};
  template <int M>
  struct static_mint {
    static_assert(0 < M, "Module must be positive");
    using mint = static_mint;
    int val;
    static_mint(): val() {}
    static_mint(long long x): val(x % M) { if (val < 0) val += M; }
    mint pow(long long n) const {
      mint ans = 1, x( * this);
      while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n /= 2;
      }
      return ans;
    }
    mint inv() const {
      return pow(M - 2);
    }
    friend mint pow(const mint & m, long long n) {
      return m.pow(n);
    }
    friend mint inv(const mint & m) {
      return m.inv();
    }
    mint operator + () const {
      mint m;
      m.val = val;
      return m;
    }
    mint operator - () const {
      mint m;
      m.val = M - val;
      return m;
    }
    mint & operator += (const mint & m) {
      if ((val += m.val) >= M) val -= M;
      return *this;
    }
    mint & operator -= (const mint & m) {
      if ((val -= m.val) < 0) val += M;
      return *this;
    }
    mint & operator *= (const mint & m) {
      val = (long long) val * m.val % M;
      return *this;
    }
    mint & operator /= (const mint & m) {
      val = (long long) val * m.inv().val % M;
      return *this;
    }
    friend mint operator + (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) += rhs;
    }
    friend mint operator - (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) -= rhs;
    }
    friend mint operator * (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) *= rhs;
    }
    friend mint operator / (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) /= rhs;
    }
    friend bool operator == (const mint & lhs,
      const mint & rhs) {
      return lhs.val == rhs.val;
    }
    friend bool operator != (const mint & lhs,
      const mint & rhs) {
      return lhs.val != rhs.val;
    }
    mint & operator++() {
      return *this += 1;
    }
    mint & operator--() {
      return *this -= 1;
    }
    mint operator++(int) {
      mint result( * this);* this += 1;
      return result;
    }
    mint operator--(int) {
      mint result( * this);* this -= 1;
      return result;
    }
    template <typename T> explicit operator T() const {
      return T(val);
    }
    friend std::ostream & operator << (std::ostream & os,
      const mint & m) {
      return os << m.val;
    }
    friend std::istream & operator >> (std::istream & is, mint & m) {
      long long x;
      is >> x;
      m = x;
      return is;
    }
  };
  template <int M> struct is_modular < static_mint <M>>: std::true_type {};
  template <int& _M> struct dynamic_mint {
    static constexpr int& M = _M;
    using mint = dynamic_mint;
    int val;
    dynamic_mint(): val() {}
    dynamic_mint(long long x): val(x % M) {
      if (val < 0) {
        val += M;
      }
    }
    mint pow(long long n) const {
      mint ans = 1, x( * this);
      while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n /= 2;
      }
      return ans;
    }
    mint inv() const {
      return pow(M - 2);
    }
    friend mint pow(const mint & m, long long n) {
      return m.pow(n);
    }
    friend mint inv(const mint & m) {
      return m.inv();
    }
    mint operator + () const {
      mint m;
      m.val = val;
      return m;
    }
    mint operator - () const {
      mint m;
      m.val = M - val;
      return m;
    }
    mint & operator += (const mint & m) {
      if ((val += m.val) >= M) val -= M;
      return *this;
    }
    mint & operator -= (const mint & m) {
      if ((val -= m.val) < 0) val += M;
      return *this;
    }
    mint & operator *= (const mint & m) {
      val = (long long) val * m.val % M;
      return *this;
    }
    mint & operator /= (const mint & m) {
      val = (long long) val * m.inv().val % M;
      return *this;
    }
    friend mint operator + (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) += rhs;
    }
    friend mint operator - (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) -= rhs;
    }
    friend mint operator * (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) *= rhs;
    }
    friend mint operator / (const mint & lhs,
      const mint & rhs) {
      return mint(lhs) /= rhs;
    }
    friend bool operator == (const mint & lhs,
      const mint & rhs) {
      return lhs.val == rhs.val;
    }
    friend bool operator != (const mint & lhs,
      const mint & rhs) {
      return lhs.val != rhs.val;
    }
    mint & operator++() {
      return *this += 1;
    }
    mint & operator--() {
      return *this -= 1;
    }
    mint operator++(int) {
      mint result( * this);* this += 1;
      return result;
    }
    mint operator--(int) {
      mint result( * this);* this -= 1;
      return result;
    }
    template <typename T> explicit operator T() const {
      return T(val);
    }
    friend std::ostream & operator << (std::ostream & os,
      const mint & m) {
      return os << m.val;
    }
    friend std::istream & operator >> (std::istream & is, mint & m) {
      long long x;
      is >> x;
      m = x;
      return is;
    }
  };
};
using im = modular::static_mint<998244353>;
constexpr int N = 503;
int n;
int a[N];
im dp1[2][N];
im dp2[2][N];
// dp1 = ways to get to i with j to cover
int b[N];
im p2[N];
im solve_case(int k) {
  for (int i = 1; i <= n; i ++) {
    if (a[i] == -1)
      b[i] = -1;
    else {
      if (a[i] < a[k] || (a[i] == a[k] && i < k))
        b[i] = 1;
      else
        b[i] = 0;
    }
  }
  for (int i = 0; i < 2; i ++)
    for (int j = 0; j <= n; j ++) {
      dp1[i][j] = 0;
      dp2[i][j] = 0;
    }
  dp1[0][0] = 1;
  int cur = 0, nxt = 1;
  for (int i = 0; i + 1 < k; i ++) {
    for (int j = 0; j <= n; j ++) {
      // dont take
      dp1[nxt][j] += dp1[cur][j];
      // take
      if (b[i + 1] == -1)
        dp1[nxt][max(0, j + b[i + 1])] += dp1[cur][j];
      else if (j + b[i + 1] <= n)
        dp1[nxt][j + b[i + 1]] += dp1[cur][j];
      dp1[cur][j] = 0;
    }
    swap(cur, nxt);
  }
  if (k == n) {
    return p2[k - 1];
  }
  for (int i = 0; i < n; i ++)
    dp2[cur][i + 1] = dp1[cur][i];
  for (int i = k; i < n; i ++) {
    for (int j = 1; j <= n; j ++) {
      // only those alive matters
      // skip then
      dp2[nxt][j] += dp2[cur][j];
      // take
      if (b[i + 1] == -1)
        dp2[nxt][j - 1] += dp2[cur][j];
      else {
        if (j + b[i + 1] <= n)
          dp2[nxt][j + b[i + 1]] += dp2[cur][j];
      }
      dp2[cur][j] = 0;
    }
    swap(cur, nxt);
  }
  im res = 0;
  for (int i = 1; i <= n; i ++)
    res += dp2[cur][i];
  return res;
}
void solution() {
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    string s;
    cin >> s;
    if (s[0] == '-') a[i] = -1;
    else {
      cin >> a[i];
    }
  }
  im ans = 0;
  for (int i = 1; i <= n; i ++)
    if (a[i] != -1)
      ans += solve_case(i) * a[i];
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); int tc = 1;
#ifdef DEBUG
  freopen("input.txt", "r", stdin); 
#endif
  p2[0] = 1;
  for (int i = 1; i < N; i ++) p2[i] = p2[i - 1] * 2;
  // cin >> tc; 
  while (tc --) { solution(); cout << "\n"; }
}
```