#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define repn(i,n) for(int i=0;i<n;i++)
#define pern(i,n) for(int i=n-1;i>=0;i--)
#define sz(x) (x).size()
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define ls i << 1
#define rs i << 1 | 1
#define pb push_back
#define pii pair<int,int>
#define pdd pair<double,double>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define mod 998244353

#define int long long

typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
int tt, test_case;

inline int rd() {
  int x = 0, f = 1; char ch = getchar();
  while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
void read(vi&v) {for(auto&x:v)x=rd();}
void print(vi&v) {for(auto&x:v)cout<<x<<' ';puts("");}
template <typename T> inline void chmx(T &x, T y) {if (y > x) x = y;}
template <typename T> inline void chmi(T &x, T y) {if (y < x) x = y;}
int ceil(int a, int b) {if ((a>0)^(b>0))return-1*(abs(a)/abs(b));return(abs(a)+abs(b)-1)/abs(b);}
int floor(int a, int b) {if ((a>0)^(b>0))return-1*((abs(a)+abs(b)-1)/abs(b));return(abs(a)/abs(b));}
int gcd(int a, int b) {return b?gcd(b,a%b):a;} int lcm(int a, int b) {return a*b/gcd(a,b);}
ll mul(ll a, ll b, int m) {ll ret = 0ll;while(b){if(b&1)ret+=a,ret%=m;a+=a,a%=m,b>>=1;}return ret;}
ll mul(ll a, ll b) {ll ret = 0ll;while(b){if(b&1)ret+=a;a+=a,b>>=1;}return ret;}
ll ksm(ll a, ll b, int m) {ll ret = 1ll;while(b){if (b&1) ret*=a,ret%=m;a*=a,a%=m,b>>=1;}return ret;}
ll ksm(ll a, ll b) {ll ret = 1ll;while(b){if(b&1)ret*=a;a*=a,b>>=1;}return ret;}
ll inv(ll x, int m) {return ksm(x,m-2,m);}

void run(int kase) {
  int n = rd();
  vi a(n, 0);
  repn(i, n) {
    char op;
    cin >> op;
    if (op == '+') {
      cin >> a[i];
    }
  }
  // 用dp求每个a[i]对答案的贡献。 
  int ans = 0; 
  repn(i, n) { // 枚举a[i],对每个a[i]求贡献,贡献为方案数*a[i]。 
    if (!a[i]) continue; // '-' 操作无需计算贡献。
     vi dp(n + 1, 0); // 用于计算方案 
     // dp[j][k]表示a[i]在所选集合中且考虑前j个操作后剩下小于a[i]的元素(或者称为比a[i]先删除的元素)个数为k个的方案数。 
     dp[0] = 1; // 初值：无操作无小于a[i]的元素的时候集合中只有一个a[i]的方案数为1。 
     // dp[j][x]仅由dp[j-1][x]转移而来,因此可以把j滚动优化。 
     repn(j, n) { // 从小到大枚举前j个操作,该维是dp的阶段。 
       if (j == i) continue; // a[i]本身不用考虑 
       if (!a[j]) { // 考虑'-'操作。 
          if (j < i) (dp[0] += dp[0]) %= mod; 
          // 无法再'-'的情况：如果'-'在a[i]之前,则该操作之后集合元素仍为0,该操作选/不选为两种情况,即dp[0](原来的情况)+=dp[0](选了之后的情况),否则若'-'在a[i]之后会将a[i]删除则不会计入方案。
          for (int k = 0; k < n; k++) (dp[k] += dp[k + 1]) %= mod;
          // 可以'-'的情况：'-'操作后,假设原来有k+1个小于a[i]的元素,减少一个后变为k个,因此所有dp[k]+=dp[k+1],正序枚举保证了每次增加的是上一阶段的dp值。 
       } else if (a[j] < a[i] || (a[j] == a[i] && j < i)) { // 如果当前元素在遇到'-'时会比a[i]先删除。 
          // 考虑将改元素加入集合,假设原来集合有x-1个小于a[i]的元素,添加该元素之后变为x个,即dp[x]+=dp[x-1],此时为了保证使用的是上一阶段的值需要倒序枚举。 
          for (int k = n; k > 0; k--) (dp[k] += dp[k - 1]) %= mod;
       } else {
          // 否则该元素加入集合之后一定比a[i]后删除,假设原来集合有x个元素,方案为dp[x],该元素加入任何一个方案该方案都仍然成立,因此dp[x](原来的方案)+=dp[x](加入该元素后的方案)。 
          for (int i = 0; i < n; i++) (dp[i] += dp[i]) %= mod;
       }
     }
     int tot = 0; repn(k, n) (tot += dp[k]) %= mod; // 计算方案。 
     (ans += tot * (a[i] % mod) % mod) %= mod; // 加入贡献 = 方案数 * a[i]。 
  }
  cout << ans << '\n';
}

signed main(){
//  tt = rd();rep(test_case,1,tt)
  run(test_case);
  return 0;
}
### 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>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define repn(i,n) for(int i=0;i<n;i++)
#define pern(i,n) for(int i=n-1;i>=0;i--)
#define sz(x) (x).size()
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define ls i << 1
#define rs i << 1 | 1
#define pb push_back
#define pii pair<int,int>
#define pdd pair<double,double>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define mod 998244353

#define int long long

typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
int tt, test_case;

inline int rd() {
  int x = 0, f = 1; char ch = getchar();
  while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
void read(vi&v) {for(auto&x:v)x=rd();}
void print(vi&v) {for(auto&x:v)cout<<x<<' ';puts("");}
template <typename T> inline void chmx(T &x, T y) {if (y > x) x = y;}
template <typename T> inline void chmi(T &x, T y) {if (y < x) x = y;}
int ceil(int a, int b) {if ((a>0)^(b>0))return-1*(abs(a)/abs(b));return(abs(a)+abs(b)-1)/abs(b);}
int floor(int a, int b) {if ((a>0)^(b>0))return-1*((abs(a)+abs(b)-1)/abs(b));return(abs(a)/abs(b));}
int gcd(int a, int b) {return b?gcd(b,a%b):a;} int lcm(int a, int b) {return a*b/gcd(a,b);}
ll mul(ll a, ll b, int m) {ll ret = 0ll;while(b){if(b&1)ret+=a,ret%=m;a+=a,a%=m,b>>=1;}return ret;}
ll mul(ll a, ll b) {ll ret = 0ll;while(b){if(b&1)ret+=a;a+=a,b>>=1;}return ret;}
ll ksm(ll a, ll b, int m) {ll ret = 1ll;while(b){if (b&1) ret*=a,ret%=m;a*=a,a%=m,b>>=1;}return ret;}
ll ksm(ll a, ll b) {ll ret = 1ll;while(b){if(b&1)ret*=a;a*=a,b>>=1;}return ret;}
ll inv(ll x, int m) {return ksm(x,m-2,m);}

void run(int kase) {
  int n = rd();
  vi a(n, 0);
  repn(i, n) {
    char op;
    cin >> op;
    if (op == '+') {
      cin >> a[i];
    }
  }
  // 用dp求每个a[i]对答案的贡献。 
  int ans = 0; 
  repn(i, n) { // 枚举a[i],对每个a[i]求贡献,贡献为方案数*a[i]。 
    if (!a[i]) continue; // '-' 操作无需计算贡献。
     vi dp(n + 1, 0); // 用于计算方案 
     // dp[j][k]表示a[i]在所选集合中且考虑前j个操作后剩下小于a[i]的元素(或者称为比a[i]先删除的元素)个数为k个的方案数。 
     dp[0] = 1; // 初值：无操作无小于a[i]的元素的时候集合中只有一个a[i]的方案数为1。 
     // dp[j][x]仅由dp[j-1][x]转移而来,因此可以把j滚动优化。 
     repn(j, n) { // 从小到大枚举前j个操作,该维是dp的阶段。 
       if (j == i) continue; // a[i]本身不用考虑 
       if (!a[j]) { // 考虑'-'操作。 
          if (j < i) (dp[0] += dp[0]) %= mod; 
          // 无法再'-'的情况：如果'-'在a[i]之前,则该操作之后集合元素仍为0,该操作选/不选为两种情况,即dp[0](原来的情况)+=dp[0](选了之后的情况),否则若'-'在a[i]之后会将a[i]删除则不会计入方案。
          for (int k = 0; k < n; k++) (dp[k] += dp[k + 1]) %= mod;
          // 可以'-'的情况：'-'操作后,假设原来有k+1个小于a[i]的元素,减少一个后变为k个,因此所有dp[k]+=dp[k+1],正序枚举保证了每次增加的是上一阶段的dp值。 
       } else if (a[j] < a[i] || (a[j] == a[i] && j < i)) { // 如果当前元素在遇到'-'时会比a[i]先删除。 
          // 考虑将改元素加入集合,假设原来集合有x-1个小于a[i]的元素,添加该元素之后变为x个,即dp[x]+=dp[x-1],此时为了保证使用的是上一阶段的值需要倒序枚举。 
          for (int k = n; k > 0; k--) (dp[k] += dp[k - 1]) %= mod;
       } else {
          // 否则该元素加入集合之后一定比a[i]后删除,假设原来集合有x个元素,方案为dp[x],该元素加入任何一个方案该方案都仍然成立,因此dp[x](原来的方案)+=dp[x](加入该元素后的方案)。 
          for (int i = 0; i < n; i++) (dp[i] += dp[i]) %= mod;
       }
     }
     int tot = 0; repn(k, n) (tot += dp[k]) %= mod; // 计算方案。 
     (ans += tot * (a[i] % mod) % mod) %= mod; // 加入贡献 = 方案数 * a[i]。 
  }
  cout << ans << '\n';
}

signed main(){
//  tt = rd();rep(test_case,1,tt)
  run(test_case);
  return 0;
}
```