#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;i++)
#define pool(i, a, b) for(ll i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 55
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
vc<vc<ll>> matmat(vc<vc<ll>> a, vc<vc<ll>> b){
    ll m=a.size();
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) loop(j, 0, m) loop(k, 0, m){
        ans[i][j]+=a[i][k] * b[k][j];
        ans[i][j]%=mod;
    }
    return ans;
}
vc<ll> matvec(vc<vc<ll>> a, vc<ll> v){
    ll m=v.size();
    vc<ll> ans(m, 0);
    loop(i, 0, m) loop(j, 0, m) ans[i]+=v[j] * a[i][j], ans[i]%=mod;
    return ans;
}
ll sum(vc<ll> a){
    ll ret=0;
    fore(v, a) ret+=v, ret%=mod;
    return ret;
}
vc<vc<ll>> matexp(vc<vc<ll>> a, ll ex){
    ll m=a.size();
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) ans[i][i]=1;
    while(ex){
        if(ex&1) ans=matmat(ans, a);
        a=matmat(a, a);
        ex/=2;
    }
    return ans;
}
void prmat(vc<vc<ll>> mat){
    ll m=mat.size();
    cout << endl;
    loop(i, 0, m){
        loop(j, 0, m) cout << mat[i][j]<<" ";
        cout << endl;
    }
    cout << endl;
}
ll solve(vc<ll> d){
    ll m=d.size();
    //cout << m << endl;
    set<ll> spremset;
    par ints[m];
    vc<ll> zac(m, 0);
    ll cur=0;
    loop(i, 0, m){
        if(cur==0)zac[i]=1;
        ints[i].fi=cur;
        cur+=d[i];
        ints[i].se=cur;
        
        if(ints[i].fi>ints[i].se) swap(ints[i].fi, ints[i].se);
        if(i==m-1)ints[i].se++;
        if(d[i]<0) ints[i].fi++, ints[i].se++;
        /*if(d[i]>=0) ints[i].se++;
        else ints[i].fi++;*/
        
        //poglej še primer ko je d=0
        
        spremset.insert(ints[i].fi);
        spremset.insert(ints[i].se);
    }
    
    spremset.erase(0);spremset.insert(1);
    vc<ll> sprem(all(spremset));
    
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) ans[i][i]=1;
    loop(i, 0, (ll)sprem.size()-1){
        
        vc<vc<ll>> mat(m, t);
        loop(j, 0, m) if(ints[j].fi<=sprem[i] and sprem[i]<ints[j].se){
            loop(k, 0, j) mat[j][k]=1;
            if(d[j]>=0) mat[j][j]=1;
        }
        
        //prmat(mat);
        ans=matmat(matexp(mat, sprem[i+1]-sprem[i]), ans);
        
    }
    return sum(matvec(ans, zac));
}
int main() {
    ll n;cin >> n;
    ll x;cin >> x;
    
    ll d[n];loop(i, 0, n) cin >> d[i];
    
    //special case
    ll br=1;
    loop(i, 0, n) if(d[i]>0) br=0;
    if(br){
        ll vsota=0;
        loop(i, 0, n) vsota+=-d[i];
        cout << 1 << " " << (vsota+1)%mod<<endl;
        return 0;
    }
    
    ll le=0;
    loop(i, 0, n){
        ll cur=0;
        loop(j, i, n) cur+=d[j], le=max(le, cur);
    }
    cout << le+1<<" ";
    
    ll nac=0;
    loop(i, 0, n){
        ll cur=0, las=-1;
        loop(j, i, n){ cur+=d[j]; if(cur==le) las=j;}
        if(las!=-1){
            vc<ll> neki;
            loop(k, i, las+1) if(d[k])neki.ps(d[k]);
            nac+=solve(neki);nac%=mod;
            i=las;
        }
    }
    cout << nac << endl;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

Igor had a sequence d_1, d_2, ..., d_n of integers. When Igor entered the classroom there was an integer x written on the blackboard.

Igor generated sequence p using the following algorithm: 

  1. initially, p = [x]; 
  2. for each 1 ≤ i ≤ n he did the following operation |d_i| times: 
    * if d_i ≥ 0, then he looked at the last element of p (let it be y) and appended y + 1 to the end of p; 
    * if d_i < 0, then he looked at the last element of p (let it be y) and appended y - 1 to the end of p. 



For example, if x = 3, and d = [1, -1, 2], p will be equal [3, 4, 3, 4, 5].

Igor decided to calculate the length of the longest increasing subsequence of p and the number of them.

A sequence a is a subsequence of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

A sequence a is an increasing sequence if each element of a (except the first one) is strictly greater than the previous element.

For p = [3, 4, 3, 4, 5], the length of longest increasing subsequence is 3 and there are 3 of them: [\underline{3}, \underline{4}, 3, 4, \underline{5}], [\underline{3}, 4, 3, \underline{4}, \underline{5}], [3, 4, \underline{3}, \underline{4}, \underline{5}].

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the length of the sequence d.

The second line contains a single integer x (-10^9 ≤ x ≤ 10^9) — the integer on the blackboard.

The third line contains n integers d_1, d_2, …, d_n (-10^9 ≤ d_i ≤ 10^9).

Output

Print two integers: 

  * the first integer should be equal to the length of the longest increasing subsequence of p; 
  * the second should be equal to the number of them modulo 998244353. 



You should print only the second number modulo 998244353.

Examples

Input


3
3
1 -1 2


Output


3 3


Input


3
100
5 -3 6


Output


9 7


Input


3
1
999999999 0 1000000000


Output


2000000000 1


Input


5
34
1337 -146 42 -69 228


Output


1393 3876

Note

The first test case was explained in the statement.

In the second test case p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108].

In the third test case p = [1, 2, …, 2000000000].

### Response

```cpp
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;i++)
#define pool(i, a, b) for(ll i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 55
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
vc<vc<ll>> matmat(vc<vc<ll>> a, vc<vc<ll>> b){
    ll m=a.size();
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) loop(j, 0, m) loop(k, 0, m){
        ans[i][j]+=a[i][k] * b[k][j];
        ans[i][j]%=mod;
    }
    return ans;
}
vc<ll> matvec(vc<vc<ll>> a, vc<ll> v){
    ll m=v.size();
    vc<ll> ans(m, 0);
    loop(i, 0, m) loop(j, 0, m) ans[i]+=v[j] * a[i][j], ans[i]%=mod;
    return ans;
}
ll sum(vc<ll> a){
    ll ret=0;
    fore(v, a) ret+=v, ret%=mod;
    return ret;
}
vc<vc<ll>> matexp(vc<vc<ll>> a, ll ex){
    ll m=a.size();
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) ans[i][i]=1;
    while(ex){
        if(ex&1) ans=matmat(ans, a);
        a=matmat(a, a);
        ex/=2;
    }
    return ans;
}
void prmat(vc<vc<ll>> mat){
    ll m=mat.size();
    cout << endl;
    loop(i, 0, m){
        loop(j, 0, m) cout << mat[i][j]<<" ";
        cout << endl;
    }
    cout << endl;
}
ll solve(vc<ll> d){
    ll m=d.size();
    //cout << m << endl;
    set<ll> spremset;
    par ints[m];
    vc<ll> zac(m, 0);
    ll cur=0;
    loop(i, 0, m){
        if(cur==0)zac[i]=1;
        ints[i].fi=cur;
        cur+=d[i];
        ints[i].se=cur;
        
        if(ints[i].fi>ints[i].se) swap(ints[i].fi, ints[i].se);
        if(i==m-1)ints[i].se++;
        if(d[i]<0) ints[i].fi++, ints[i].se++;
        /*if(d[i]>=0) ints[i].se++;
        else ints[i].fi++;*/
        
        //poglej še primer ko je d=0
        
        spremset.insert(ints[i].fi);
        spremset.insert(ints[i].se);
    }
    
    spremset.erase(0);spremset.insert(1);
    vc<ll> sprem(all(spremset));
    
    vc<ll> t(m, 0);
    vc<vc<ll>> ans(m, t);
    loop(i, 0, m) ans[i][i]=1;
    loop(i, 0, (ll)sprem.size()-1){
        
        vc<vc<ll>> mat(m, t);
        loop(j, 0, m) if(ints[j].fi<=sprem[i] and sprem[i]<ints[j].se){
            loop(k, 0, j) mat[j][k]=1;
            if(d[j]>=0) mat[j][j]=1;
        }
        
        //prmat(mat);
        ans=matmat(matexp(mat, sprem[i+1]-sprem[i]), ans);
        
    }
    return sum(matvec(ans, zac));
}
int main() {
    ll n;cin >> n;
    ll x;cin >> x;
    
    ll d[n];loop(i, 0, n) cin >> d[i];
    
    //special case
    ll br=1;
    loop(i, 0, n) if(d[i]>0) br=0;
    if(br){
        ll vsota=0;
        loop(i, 0, n) vsota+=-d[i];
        cout << 1 << " " << (vsota+1)%mod<<endl;
        return 0;
    }
    
    ll le=0;
    loop(i, 0, n){
        ll cur=0;
        loop(j, i, n) cur+=d[j], le=max(le, cur);
    }
    cout << le+1<<" ";
    
    ll nac=0;
    loop(i, 0, n){
        ll cur=0, las=-1;
        loop(j, i, n){ cur+=d[j]; if(cur==le) las=j;}
        if(las!=-1){
            vc<ll> neki;
            loop(k, i, las+1) if(d[k])neki.ps(d[k]);
            nac+=solve(neki);nac%=mod;
            i=las;
        }
    }
    cout << nac << endl;
}
```