Problem: 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].

Solution (in CPP):

Solution:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define infL (1LL<<60)
#define inf (1<<30)
#define inf9 (1000000000)
#define MOD 998244353//1000000007
#define EPS 1e-9
#define Gr 9.8
#define PI acos(-1)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REQ(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define readmp(n) for(int i=0,u,v;i<n;i++) {scanf("%d%d",&u,&v); mp[u].push_back(v); mp[v].push_back(u);}
typedef  long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef ld ValType;
template<typename  T> void maxtt(T& t1, T t2) {
    t1=max(t1,t2);
}
template<typename  T> void mintt(T& t1, T t2) {
    t1=min(t1,t2);
}
#define MAX (135)

bool debug = 0;
int n,m,k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
string direc="RDLU";
const ll MOD2 = (ll)MOD * (ll)MOD;
ll ln, lk, lm;
void etp(bool f = 0) {
    puts(f ?"YES" : "NO");
    exit(0);
}
void addmod(int &x, int y, int mod = MOD){
    x+=y; if (x>=mod) x-=mod;
    if(x<0) x+=mod;
    assert(x>=0 && x<mod);
}
void et(int x=-1) {
    printf("%d\n", x); exit(0);
}
ll fastPow(ll x, ll y, int mod=MOD) {
    ll ans = 1;
    while(y>0) {
        if(y&1) ans = (x * ans)%mod;
        x = x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gcd1(ll x, ll y) {
    return y?gcd1(y,x%y):x;
}




struct Matrix {
    int n,m;
    int a[55][55];
    Matrix() { }
    Matrix(int n, int m) : n(n), m(m) { }
    void init(int num) {
        REP(i,n)REP(j,m)a[i][j]=num;
    }
    
    Matrix operator*(Matrix b) {
        Matrix o = Matrix(n, b.m);
        for(int i=0;i<n;i++) {
            for(int j=0;j<b.m;j++) {
                o.a[i][j]=0;
                for(int k=0;k<m;k++) {
                    addmod(o.a[i][j], (ll)a[i][k] * b.a[k][j] % MOD);
                }
            }
        }
        return o;
    }
    Matrix pow(ll p) {
        Matrix o = Matrix(n,m);
        Matrix b = *this;
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) o.a[i][j] = (i==j);
        while(p>0) {
            if (p&1) o=o*b;
            b=b*b; p>>=1;
        }
        return o;
    }
};
vector<int> a;
int cal(int l, int r) {
    int len = r-l+1;
    vector<pll> vp;
    ll pre=0;
    for(int i=l;i<=r;i++) {
        vp.push_back({pre+ (a[i]<0 ? -1 : 1), pre+a[i]}); pre+=a[i];
    }
    vp[0].first=0;
    vector<ll> V;
    REP(i, vp.size()) {
        V.push_back(vp[i].first-1);V.push_back(vp[i].first);
        V.push_back(vp[i].first+1); V.push_back(vp[i].second-1);
        V.push_back(vp[i].second); V.push_back(vp[i].second+1);
    }
    sort(V.begin(), V.end());
    int N = unique(V.begin(),V.end())-V.begin();
    Matrix mans = Matrix(1, len+1);
    mans.init(0); mans.a[0][0]=1;
    pre=-1;
    REP(i,N-1) {
        Matrix mt = Matrix(len+1,len+1);
        mt.init(0);
        REP(j, vp.size()) {
            ll mi = min(vp[j].first, vp[j].second);
            ll ma = max(vp[j].first, vp[j].second);
            if (mi <= pre+1 && ma >= V[i]) {
                if(vp[j].first < vp[j].second) {
                    for(int k=0;k<=j+1;k++) mt.a[k][j+1]=1;
                } else {
                    for(int k=0;k<=j;k++) mt.a[k][j+1]=1;
                }
            }
        }
        mt = mt.pow(V[i]-pre); pre=V[i];
        mans = mans * mt;
    }
    int A=0;
    REP(i,len+1) addmod(A, mans.a[0][i]);
    return A;
}
void fmain(int tid) {
    int x;
    scanf("%d%d", &n, &x);
    REQ(i,n) {
        scanf("%d", &x);
        if(x!=0) a.push_back(x);
    }
    n=(int)a.size();
    ll S=0,ans=0;
    REP(i,n) {
        ll tmp = S;
        for(int j=i;j<n;j++) {
            tmp += a[j];
            maxtt(ans, tmp-S);
        }
        S+=a[i];
    }
    if (ans==0) {
        int w=1;
        REP(i,n) {
            addmod(w, abs(a[i]));
        }
        printf("1 %d\n", w); return;
    }
    S=0;
    int ws=0;
    for(int i=0;i<n;i++) {
        ll tmp = S; int to=-1;
        for(int j=i;j<n;j++) {
            tmp += a[j];
            if(ans == tmp-S) {
                to=j;
            }
        }
        S+=a[i];
        if (to != -1) {
            addmod(ws, cal(i,to)); i=to;
        }
    }
    printf("%lld %d\n",ans+1, ws);
}
int main() {
    int t=1;
//    init();
//    scanf("%d", &t);
//    init();
    REQ(i,t) {
        fmain(i);
    }
    return 0;
}