#include<bits/stdc++.h>

/*#include<iostream>
#include<vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
//using namespace __gnu_pbds;

#define PB push_back
using namespace std;

#define loop(i , x , n) for(ll i = x;i< n;i++)
#define loopc(i , x , n) for(ll i = x;i<= n;i++)
#define loopr(i , x , n) for(ll i = n;i>=x ;i--)

#define ll long long
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef pair<ll, ll> pll;
#define mp(x, y) make_pair<long long , long long >(x, y)
#define SIN(x) sin(x * 3.141592653589793238)
#define COS(x) cos(x * 3.141592653589793238)
#define endl "\n"
#define ff first
#define ss second
#define ELGO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc ll tc; cin>>tc; while(tc--)
#define vv(x) vector<x>
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof  pop_front
#define endl "\n"
#define umap unordered_map
#define pq priority_queue
#define ca(a,n) for(ll i=0;i<n;i++){ cin>>a[i]; }
#define ca1(a,n) for(ll i=1;i<=n;i++){ cin>>a[i]; }
#define svec(x) sort(x.begin(), x.end())
#define rsvec(x) sort(x.begin(), x.end(), greater<ll>())
#define all(x) (x).begin(), (x).end()
//vector<string>dp;

const ll inf=1e18;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
    os << "[";
    for (ll i=0; i < v.size(); ++i) {
        os << v[i];
        if (i != v.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v){
    os << "{";
    for (auto it : v) {
        os << it;
        if (it != *v.rbegin())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const map<T, S>& v){
    os<<"{";
    for (auto it : v){
        os << it.first << " : "
           << it.second ;
        if (it != *v.rbegin())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const pair<T, S>& v){
    os << "(";
    os << v.first << ", "
       << v.second << ")";
    return os;
}


//const ll mod = 998244353;


ll fin(ll a, vv(pll)&par ){
    if(par[a].ff==a)return a;
    else return fin(par[a].ff, par);
}
bool uni(ll a ,ll b,vv(pll)&par ){
    ll o = fin(a, par);
    ll t = fin(b, par);
    if(o==t)return true;
    if(par[t].ss > par[o].ss)swap(o,t);
    if(par[t].ss==par[o].ss)par[o].ss++;
    par[t].ff = o;
    return false;
}
ll power(ll x, ll y, ll m)
{
    if (y == 0)
        return 1;
    ll p = power(x, y / 2, m) % m;
    p = (p * p) % m;

    return (y % 2 == 0) ? p : (x * p) % m;
}


ll fin_par(vv(vv(ll))&bin, ll a , ll p){
    ll c= a;
    loop(i, 0, 22){
        if((1<<i) & p){
            c = bin[c][i];
        }
    }
    return c;
}

ll lca(vv(vv(ll))&bin, ll a, ll b , vv(ll)&d){
    if(d[a]> d[b]){

        swap(a,b);
    }

    ll dif = d[b]-d[a];

    ll prod = (1ll<<29);
    loopr(i, 0, 29){
        if(dif&prod){
            b = bin[b][i];
        }
        prod/=2;
    }

    if( b == a )return a;
    prod = (1ll<<29);
    loopr(i, 0, 29){
        if(bin[b][i]!= bin[a][i]){
            b = bin[b][i];
            a = bin[a][i];
        }
        prod/=2;
    }

    return bin[a][0];
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;



void solve(){
    ll n, a, b;
    vv(ll)v;
    cin>> n;
    char c;
    ll num;
    loop(i, 0, n){
        cin>>c;
        if(c=='-'){
            v.pb(-1);
            continue;
        }
        cin>> num;
        v.pb(num);
    }
    //watch(v);
    ll ans = 0;
    vv(ll)less_left(n+1, 0);
    vv(ll)dp(n, 0);
    ll p2 = 1;
    loop(i, 0, n){
        if( v[i]==-1){
            p2*=2;
            p2%=mod;
            continue;
        }

        loop(j, 0, n+1)less_left[j] = 0;
        less_left[0]= 1;

        loop(j , 0, n)dp[j]= 0;



        loop(j, 0, n){
            //if(v[i]==2)watch(less_left);
            if(j== i ){
                    dp[j]= p2;

            }
            else if(v[j]== -1){
                ll s = 0;
                ll temp = less_left[0];
                loop(k, 0, n){
                    less_left[k]+= less_left[k+1];
                    less_left[k]%=mod;
                    s+= less_left[k+1];
                    s%=mod;
                }
                if(j>i)dp[j]= s;
                if(j<i)less_left[0]+=temp;
                less_left[0]%=mod;
            }
            else {
                ll s = 0;
                loop(k, 0, j){s+= dp[k];s%=mod;}
                if(j>i)dp[j]= s;
                if(j<i){
                    if(v[j]<v[i]){
                        loopr(k, 1, n){
                            less_left[k]+= less_left[k-1];
                            less_left[k]%=mod;
                        }
                    }
                    else {
                        loop(k , 0, n+1){
                            less_left[k]*=2;
                            less_left[k]%=mod;
                        }
                    }
                }
                else {
                    if(v[j]<= v[i]){
                        loopr(k, 1, n){
                            less_left[k]+= less_left[k-1];
                            less_left[k]%=mod;
                        }
                    }
                    else {
                        loop(k , 0, n+1){
                            less_left[k]*=2;
                            less_left[k]%=mod;
                        }
                    }
                }

            }

        }
        ll tot_sum = 0;
        //if(v[i]==1)watch(dp);

        loop(j, 0, n){
            tot_sum+= dp[j];
            tot_sum%=mod;
        }
        ans+= ((tot_sum)*v[i])%mod;
        ans%=mod;
        //watch(tot_sum);
        p2*=2;
        p2%=mod;
    }
    cout<<ans<<endl;

}


int main()
{
    ELGO
    //pre();
    //cout<<"YO"<<endl;
    //tc{
        solve();
    //}



}

### Prompt

Construct a cpp code solution to the problem outlined:

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<iostream>
#include<vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
//using namespace __gnu_pbds;

#define PB push_back
using namespace std;

#define loop(i , x , n) for(ll i = x;i< n;i++)
#define loopc(i , x , n) for(ll i = x;i<= n;i++)
#define loopr(i , x , n) for(ll i = n;i>=x ;i--)

#define ll long long
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef pair<ll, ll> pll;
#define mp(x, y) make_pair<long long , long long >(x, y)
#define SIN(x) sin(x * 3.141592653589793238)
#define COS(x) cos(x * 3.141592653589793238)
#define endl "\n"
#define ff first
#define ss second
#define ELGO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc ll tc; cin>>tc; while(tc--)
#define vv(x) vector<x>
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof  pop_front
#define endl "\n"
#define umap unordered_map
#define pq priority_queue
#define ca(a,n) for(ll i=0;i<n;i++){ cin>>a[i]; }
#define ca1(a,n) for(ll i=1;i<=n;i++){ cin>>a[i]; }
#define svec(x) sort(x.begin(), x.end())
#define rsvec(x) sort(x.begin(), x.end(), greater<ll>())
#define all(x) (x).begin(), (x).end()
//vector<string>dp;

const ll inf=1e18;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
    os << "[";
    for (ll i=0; i < v.size(); ++i) {
        os << v[i];
        if (i != v.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v){
    os << "{";
    for (auto it : v) {
        os << it;
        if (it != *v.rbegin())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const map<T, S>& v){
    os<<"{";
    for (auto it : v){
        os << it.first << " : "
           << it.second ;
        if (it != *v.rbegin())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const pair<T, S>& v){
    os << "(";
    os << v.first << ", "
       << v.second << ")";
    return os;
}


//const ll mod = 998244353;


ll fin(ll a, vv(pll)&par ){
    if(par[a].ff==a)return a;
    else return fin(par[a].ff, par);
}
bool uni(ll a ,ll b,vv(pll)&par ){
    ll o = fin(a, par);
    ll t = fin(b, par);
    if(o==t)return true;
    if(par[t].ss > par[o].ss)swap(o,t);
    if(par[t].ss==par[o].ss)par[o].ss++;
    par[t].ff = o;
    return false;
}
ll power(ll x, ll y, ll m)
{
    if (y == 0)
        return 1;
    ll p = power(x, y / 2, m) % m;
    p = (p * p) % m;

    return (y % 2 == 0) ? p : (x * p) % m;
}


ll fin_par(vv(vv(ll))&bin, ll a , ll p){
    ll c= a;
    loop(i, 0, 22){
        if((1<<i) & p){
            c = bin[c][i];
        }
    }
    return c;
}

ll lca(vv(vv(ll))&bin, ll a, ll b , vv(ll)&d){
    if(d[a]> d[b]){

        swap(a,b);
    }

    ll dif = d[b]-d[a];

    ll prod = (1ll<<29);
    loopr(i, 0, 29){
        if(dif&prod){
            b = bin[b][i];
        }
        prod/=2;
    }

    if( b == a )return a;
    prod = (1ll<<29);
    loopr(i, 0, 29){
        if(bin[b][i]!= bin[a][i]){
            b = bin[b][i];
            a = bin[a][i];
        }
        prod/=2;
    }

    return bin[a][0];
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;



void solve(){
    ll n, a, b;
    vv(ll)v;
    cin>> n;
    char c;
    ll num;
    loop(i, 0, n){
        cin>>c;
        if(c=='-'){
            v.pb(-1);
            continue;
        }
        cin>> num;
        v.pb(num);
    }
    //watch(v);
    ll ans = 0;
    vv(ll)less_left(n+1, 0);
    vv(ll)dp(n, 0);
    ll p2 = 1;
    loop(i, 0, n){
        if( v[i]==-1){
            p2*=2;
            p2%=mod;
            continue;
        }

        loop(j, 0, n+1)less_left[j] = 0;
        less_left[0]= 1;

        loop(j , 0, n)dp[j]= 0;



        loop(j, 0, n){
            //if(v[i]==2)watch(less_left);
            if(j== i ){
                    dp[j]= p2;

            }
            else if(v[j]== -1){
                ll s = 0;
                ll temp = less_left[0];
                loop(k, 0, n){
                    less_left[k]+= less_left[k+1];
                    less_left[k]%=mod;
                    s+= less_left[k+1];
                    s%=mod;
                }
                if(j>i)dp[j]= s;
                if(j<i)less_left[0]+=temp;
                less_left[0]%=mod;
            }
            else {
                ll s = 0;
                loop(k, 0, j){s+= dp[k];s%=mod;}
                if(j>i)dp[j]= s;
                if(j<i){
                    if(v[j]<v[i]){
                        loopr(k, 1, n){
                            less_left[k]+= less_left[k-1];
                            less_left[k]%=mod;
                        }
                    }
                    else {
                        loop(k , 0, n+1){
                            less_left[k]*=2;
                            less_left[k]%=mod;
                        }
                    }
                }
                else {
                    if(v[j]<= v[i]){
                        loopr(k, 1, n){
                            less_left[k]+= less_left[k-1];
                            less_left[k]%=mod;
                        }
                    }
                    else {
                        loop(k , 0, n+1){
                            less_left[k]*=2;
                            less_left[k]%=mod;
                        }
                    }
                }

            }

        }
        ll tot_sum = 0;
        //if(v[i]==1)watch(dp);

        loop(j, 0, n){
            tot_sum+= dp[j];
            tot_sum%=mod;
        }
        ans+= ((tot_sum)*v[i])%mod;
        ans%=mod;
        //watch(tot_sum);
        p2*=2;
        p2%=mod;
    }
    cout<<ans<<endl;

}


int main()
{
    ELGO
    //pre();
    //cout<<"YO"<<endl;
    //tc{
        solve();
    //}



}

```