#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
#define X first
#define Y second 
#define nl '\n'
#define AC return 0
#define pb(a) push_back(a) 
#define mst(a,b) memset(a, b, sizeof a)
#define rep(i,n) for(int i = 0; (i)<(n); i++)
#define rep1(i,n) for(int i = 1; (i)<=(n); i++)
#define scd(a) scanf("%lld", &a)
#define scdd(a,b) scanf("%lld%lld", &a, &b)
#define scs(s) scanf("%s", s)
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const ll INF = (ll)0x3f3f3f3f3f3f3f, MAX = 9e18, MIN = -9e18;
const int N = 510, M = 2e6+10, mod = 998244353, inf = 0x3f3f3f3f;
ll dp[N], pw2[N], a[N];
string op[N];

int main()
{
	IOS;
	int _;
	// cin>>_;
	_ = 1;
	while(_--)
	{
		ll n, ans = 0;
		cin>>n;
		pw2[0] = 1;
		rep1(i, n)
		{
			cin>>op[i];
			if(op[i] == "+")
				cin>>a[i];
			pw2[i] = pw2[i-1] * 2 % mod;
		}
		//对数组定义优先级，优先级低的值在遇到'-'时会先被弹出去
		rep1(k, n)
		{
			if(op[k] == "+")//放入a[k]，考虑a[k]对其他所有集合的贡献
			{	
				mst(dp, 0);	//dp[i]表示集合中个数为i的集合数
				dp[0] = 1;	//一开始集合中个数为0的情况是1
				ll cnt = 0;
				//统计优先级比a[k]高的数的个数
				rep1(i, n)
				{
					if(i <= k)	cnt += (a[i] > a[k]);
					else	cnt += (a[i] >= a[k]);
				}
				rep1(i, n)
				{
					//优先级比a[k]高的情况已经考虑到，直接continue
					if(i == k)	continue;
					if((i <= k && a[i] > a[k]) || (i > k && a[i] >= a[k]))	continue;
					
					//优先级比a[k]低的情况
					if(op[i] == "+")
					{
						for(int i = n-1; i >= 1; i--)	dp[i] = (dp[i] + dp[i-1]) % mod;
					}
					else
					{
						if(i < k)	dp[0] = dp[0] * 2 % mod;	//k前面的'-'有选与不选两种选择，可以使得a[k]的贡献翻倍
						rep(i, n)	dp[i] = (dp[i] + dp[i+1]) % mod;
					}
				}
				rep(i, n)	ans = (ans + pw2[cnt] * dp[i] % mod * a[k]) % mod;
			}
		}
		cout<<ans<<nl;
	}
	
	
	AC;
} 

### Prompt

Your challenge is to write 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>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
#define X first
#define Y second 
#define nl '\n'
#define AC return 0
#define pb(a) push_back(a) 
#define mst(a,b) memset(a, b, sizeof a)
#define rep(i,n) for(int i = 0; (i)<(n); i++)
#define rep1(i,n) for(int i = 1; (i)<=(n); i++)
#define scd(a) scanf("%lld", &a)
#define scdd(a,b) scanf("%lld%lld", &a, &b)
#define scs(s) scanf("%s", s)
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const ll INF = (ll)0x3f3f3f3f3f3f3f, MAX = 9e18, MIN = -9e18;
const int N = 510, M = 2e6+10, mod = 998244353, inf = 0x3f3f3f3f;
ll dp[N], pw2[N], a[N];
string op[N];

int main()
{
	IOS;
	int _;
	// cin>>_;
	_ = 1;
	while(_--)
	{
		ll n, ans = 0;
		cin>>n;
		pw2[0] = 1;
		rep1(i, n)
		{
			cin>>op[i];
			if(op[i] == "+")
				cin>>a[i];
			pw2[i] = pw2[i-1] * 2 % mod;
		}
		//对数组定义优先级，优先级低的值在遇到'-'时会先被弹出去
		rep1(k, n)
		{
			if(op[k] == "+")//放入a[k]，考虑a[k]对其他所有集合的贡献
			{	
				mst(dp, 0);	//dp[i]表示集合中个数为i的集合数
				dp[0] = 1;	//一开始集合中个数为0的情况是1
				ll cnt = 0;
				//统计优先级比a[k]高的数的个数
				rep1(i, n)
				{
					if(i <= k)	cnt += (a[i] > a[k]);
					else	cnt += (a[i] >= a[k]);
				}
				rep1(i, n)
				{
					//优先级比a[k]高的情况已经考虑到，直接continue
					if(i == k)	continue;
					if((i <= k && a[i] > a[k]) || (i > k && a[i] >= a[k]))	continue;
					
					//优先级比a[k]低的情况
					if(op[i] == "+")
					{
						for(int i = n-1; i >= 1; i--)	dp[i] = (dp[i] + dp[i-1]) % mod;
					}
					else
					{
						if(i < k)	dp[0] = dp[0] * 2 % mod;	//k前面的'-'有选与不选两种选择，可以使得a[k]的贡献翻倍
						rep(i, n)	dp[i] = (dp[i] + dp[i+1]) % mod;
					}
				}
				rep(i, n)	ans = (ans + pw2[cnt] * dp[i] % mod * a[k]) % mod;
			}
		}
		cout<<ans<<nl;
	}
	
	
	AC;
} 

```