#include <bits/stdc++.h>
using namespace std;
#define io_speed_up ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
template<typename T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;} //读整型
template<typename T>void pt(T x,int c=10){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10,-1);putchar(x%10+48);if(c!=-1)putchar(c);}
template<typename T>void umax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void umin(T&x,const T&y){if(x>y)x=y;}
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define for1(i,n) for (int i=1;i<=n;i++)
#define for0(i,n) for (int i=0;i<n;i++)
#define ms(a,b)  memset(a,b,sizeof a)
#define all(n) (n).begin(), (n).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<long,long>;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 998244353 ;

struct Matrix {
    vector<vector<ll>> m;
    int n;
    Matrix(int _n) {
        n = _n;
        m = vector<vector<ll>>(n, vector<ll>(n,0));
    }
    Matrix operator*(const Matrix &o) const {
        Matrix ret(n);
        for0(i,n)
            for0(j,n)
                for0(k,n)
                    (ret.m[i][j] += m[i][k]*o.m[k][j]) %= mod;
        return ret;
    }
    void setI() {
        for0(i,n) m[i][i] = 1;
    }
    void addC(int k,int t=1) {
        for(int i=0;i<k;i++) m[i][k] = 1; 
        m[k][k] = t;
    }
    ll get_sum() {
        ll ans = 0;
        for0(i,n)
            for0(j,n)
                ans += m[i][j];
        return ans % mod;
    }
    void show() {
        for0(i,n)
            for0(j,n)
                cout<<m[i][j]<<" \n"[j==n-1];
        cout<<"...............\n";
    }
    ll get_row_sum(int k) {
        ll sum = 0;
        for(int i=0;i<n;i++)
            sum += m[k][i];
        return sum % mod;
    }
};
Matrix qp(Matrix &A,ll k) {
    Matrix ret = A;
    k--;
    while(k) {
        if(k&1) ret = ret*A;
        A=A*A;
        k>>=1;
    }
    return ret;
}

int d[100];
ll a[100];
int n,k,_;
ll max_len() {
    ll d = 1;
    rep(i,0,k)
        rep(j,i+1,k)
            umax(d, a[j]-a[i]+1);
    return d;
}
int main()
{
    io_speed_up;
    // freopen("1.in","r",stdin);
    cin>>n>>_;
    rep(i,1,n) cin>>d[i];
    int pre = 0;
    rep(i,1,n) {
        if(d[i]==0) continue;
        if(1LL*pre*d[i] > 0) a[k] += d[i];
        else {
            ++k;
            a[k] = a[k-1] + d[i];
            pre = d[i];
        }
    }

    // rep(i,0,k) cout<<a[i]<<" \n"[i==k];

    ll len = max_len();
    if(len==1) {
        ll sum = 1;
        rep(i,1,k) sum += abs(a[i]);
        cout<<1<<" "<<sum%mod<<"\n";
        return 0;
    }
    if(k==1) {
        cout<<len<<" 1\n";
        return 0;
    }


    ll ans = 0;
    set<ll> base;
    rep(i,0,k) {
        if(base.count(a[i])) continue;
        int pos = -1;
        rep(j,i,k) {
            if(a[j]-a[i]+1==len) pos = j;
        }
        if(pos==-1) continue;
        vector<ll> v;
        for(int j=i;j<=pos;j++) {
            v.push_back(a[j]);
            v.push_back(a[j]+1);
        }
        
        sort(all(v));
        v.erase(unique(all(v)),v.end());

        Matrix A(pos-i);
        A.setI();
  
        a[i]--;
        for(int h=0;h<sz(v)-1;h++) {
            ll t = v[h];
            Matrix B(pos-i);
            ll self = true;
            for(int j=i+1;j<=pos;j++) {
                if(self)  {
                    if(a[j]>=t && a[j-1]+1<=t) B.addC(j-i-1,1);
                } else if(a[j-1]-1 >= t && a[j]<=t) B.addC(j-i-1,0);
                self ^= 1;
            }
            A = A * qp(B, v[h+1] - t);
        }
        // A.show();
        ans += A.get_row_sum(0);
        base.insert(a[i]+1);
    } 
    cout<<len<<" "<<ans%mod<<"\n";
    return 0;
}
### Prompt

In Cpp, your task is to solve the following 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].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define io_speed_up ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
template<typename T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;} //读整型
template<typename T>void pt(T x,int c=10){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10,-1);putchar(x%10+48);if(c!=-1)putchar(c);}
template<typename T>void umax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void umin(T&x,const T&y){if(x>y)x=y;}
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define for1(i,n) for (int i=1;i<=n;i++)
#define for0(i,n) for (int i=0;i<n;i++)
#define ms(a,b)  memset(a,b,sizeof a)
#define all(n) (n).begin(), (n).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<long,long>;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 998244353 ;

struct Matrix {
    vector<vector<ll>> m;
    int n;
    Matrix(int _n) {
        n = _n;
        m = vector<vector<ll>>(n, vector<ll>(n,0));
    }
    Matrix operator*(const Matrix &o) const {
        Matrix ret(n);
        for0(i,n)
            for0(j,n)
                for0(k,n)
                    (ret.m[i][j] += m[i][k]*o.m[k][j]) %= mod;
        return ret;
    }
    void setI() {
        for0(i,n) m[i][i] = 1;
    }
    void addC(int k,int t=1) {
        for(int i=0;i<k;i++) m[i][k] = 1; 
        m[k][k] = t;
    }
    ll get_sum() {
        ll ans = 0;
        for0(i,n)
            for0(j,n)
                ans += m[i][j];
        return ans % mod;
    }
    void show() {
        for0(i,n)
            for0(j,n)
                cout<<m[i][j]<<" \n"[j==n-1];
        cout<<"...............\n";
    }
    ll get_row_sum(int k) {
        ll sum = 0;
        for(int i=0;i<n;i++)
            sum += m[k][i];
        return sum % mod;
    }
};
Matrix qp(Matrix &A,ll k) {
    Matrix ret = A;
    k--;
    while(k) {
        if(k&1) ret = ret*A;
        A=A*A;
        k>>=1;
    }
    return ret;
}

int d[100];
ll a[100];
int n,k,_;
ll max_len() {
    ll d = 1;
    rep(i,0,k)
        rep(j,i+1,k)
            umax(d, a[j]-a[i]+1);
    return d;
}
int main()
{
    io_speed_up;
    // freopen("1.in","r",stdin);
    cin>>n>>_;
    rep(i,1,n) cin>>d[i];
    int pre = 0;
    rep(i,1,n) {
        if(d[i]==0) continue;
        if(1LL*pre*d[i] > 0) a[k] += d[i];
        else {
            ++k;
            a[k] = a[k-1] + d[i];
            pre = d[i];
        }
    }

    // rep(i,0,k) cout<<a[i]<<" \n"[i==k];

    ll len = max_len();
    if(len==1) {
        ll sum = 1;
        rep(i,1,k) sum += abs(a[i]);
        cout<<1<<" "<<sum%mod<<"\n";
        return 0;
    }
    if(k==1) {
        cout<<len<<" 1\n";
        return 0;
    }


    ll ans = 0;
    set<ll> base;
    rep(i,0,k) {
        if(base.count(a[i])) continue;
        int pos = -1;
        rep(j,i,k) {
            if(a[j]-a[i]+1==len) pos = j;
        }
        if(pos==-1) continue;
        vector<ll> v;
        for(int j=i;j<=pos;j++) {
            v.push_back(a[j]);
            v.push_back(a[j]+1);
        }
        
        sort(all(v));
        v.erase(unique(all(v)),v.end());

        Matrix A(pos-i);
        A.setI();
  
        a[i]--;
        for(int h=0;h<sz(v)-1;h++) {
            ll t = v[h];
            Matrix B(pos-i);
            ll self = true;
            for(int j=i+1;j<=pos;j++) {
                if(self)  {
                    if(a[j]>=t && a[j-1]+1<=t) B.addC(j-i-1,1);
                } else if(a[j-1]-1 >= t && a[j]<=t) B.addC(j-i-1,0);
                self ^= 1;
            }
            A = A * qp(B, v[h+1] - t);
        }
        // A.show();
        ans += A.get_row_sum(0);
        base.insert(a[i]+1);
    } 
    cout<<len<<" "<<ans%mod<<"\n";
    return 0;
}
```