#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <deque>
#include <ctype.h>
#include <limits.h>
#include <map>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>

using namespace std;
typedef long long ll;

void solve();

void init() {
#ifdef _LOCAL_ 
    if(!freopen("case.txt", "r", stdin)) {
        perror("open file failed!:");
        exit(1);
    }
    if(!freopen("main.ans", "w", stdout)) {
        perror("open file failed!:");
        exit(1);
    }
#endif
}


template<class T> T read() {
    int ch = getchar();
    if(ch == EOF) {
        return INT_MIN;
    }
    while(!isdigit(ch) && ch != '-') {
        ch = getchar();
        if(ch == EOF) {
            return INT_MIN;
        }
    }
    T res = 0, sign = 1;
    if(ch == '-') {
        ch = getchar();
        sign = -1;
    }
    while(isdigit(ch)) {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * sign;
}

int main() {
    init();
    solve();
    return 0;
}

/*********************code start here*********************/
const int MAXN = 50;
const ll mod = 998244353;
ll inm[MAXN + 5][MAXN + 5], tmpm[MAXN + 5][MAXN + 5], outm[MAXN + 5][MAXN + 5];
void mul(int n) {
    memset(tmpm, 0, sizeof(tmpm));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = 0; k < n; ++k) {
                tmpm[i][j] += inm[i][k] * inm[k][j];
                tmpm[i][j] %= mod;
            }
        }
    }
    memcpy(inm, tmpm, sizeof(tmpm));
}
void mul2(int n) {
    memset(tmpm, 0, sizeof(tmpm));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = 0; k < n; ++k) {
                tmpm[i][j] += inm[i][k] * outm[k][j];
                tmpm[i][j] %= mod;
            }
        }
    }
    memcpy(outm, tmpm, sizeof(tmpm));
}
void qpaw(ll p, int n) {
    memset(outm, 0, sizeof(outm));
    for(int i = 0; i < n; ++i) {
        outm[i][i] = 1;
    }
    while(p) {
        if(p & 1) {
            mul2(n);
        }
        mul(n);
        p >>= 1;
    }
}

ll arr[MAXN + 5], vals[3*MAXN + 5];
int mini[MAXN + 5], st[MAXN + 5], ed[MAXN + 5], up[MAXN + 5], le[MAXN + 5];
int has[MAXN + 5][3*MAXN + 5];
ll f[MAXN + 5][3*MAXN + 5];

void solve() {
    int n = read<int>(), N = 1, sz = 0;
    arr[0] = 0;
    ll x = read<int>();
    ll pred = 0, cur = 0;
    for(int i = 0; i < n; ++i) {
        ll d = read<int>();
        if(d != 0) {
            if((pred > 0 && d > 0) || (pred < 0 && d < 0)) {
                arr[N-1] += d;
            } else {
                arr[N] = arr[N-1] + d;
                ++N;
            }
            pred = d;
        }
    }
    if(N == 1) {
        printf("1 1\n");
        return;
    }
    if(N == 2 && arr[1] < 0) {
        printf("1 %lld\n", (-arr[1] + 1) % mod);
        return;
    }
    ll minv = 0, maxd = 0;
    for(int i = 0; i < N; ++i) {
        minv = min(minv, arr[i]);
        maxd = max(maxd, arr[i] - minv);
    }
    int vcnt = 0;
    for(int i = 0; i < N; ++i) {
        vals[vcnt++] = arr[i]-1;
        vals[vcnt++] = arr[i];
        vals[vcnt++] = arr[i]+1;
    }
    sort(vals, vals + vcnt);
    vcnt = unique(vals, vals + vcnt) - vals;
    for(int i = 0; i < N; ++i) {
        arr[i] = lower_bound(vals, vals + vcnt, arr[i]) - vals;
    }
    for(int i = 1; i < N; ++i) {
        if(arr[i] > arr[i-1]) {
            st[i-1] = arr[i-1], ed[i-1] = arr[i];
            up[i-1] = 1;
        } else {
            st[i-1] = arr[i] + 1, ed[i-1] = arr[i-1] - 1;
            up[i-1] = 0;
        }
    }
    memset(f, 0, sizeof(f));
    memset(le, 0x3f, sizeof(le));
    for(int i = 0; i < N-1; ++i) {
        for(int j = 0; j <= i; ++j) {
            if(vals[ed[i]] - vals[st[j]] == maxd) {
                f[j][st[j]] = 1;
                has[i][ed[i]] = 1;
                for(int k = j; k <= i; ++k) {
                    le[k] = min(le[k], j);
                }
            }
        }
    }
    for(int j = 1; j < vcnt; ++j) {
        memset(inm, 0, sizeof(inm));
        for(int i = 0, mini = 0; i < N-1; ++i) {
            if(st[i] < st[mini]) {
                mini = i;
            }
            if(st[i] <= j && j <= ed[i]) {
                for(int k = i-1; k >= le[i]; --k) {
                    if(st[k] <= j-1 && ed[k] >= j-1) {
                        inm[i][k] = 1;
                    }
                }
                if(up[i] && st[i] <= j-1) {
                    inm[i][i] = 1;
                }
            }
        }
        if(vals[j] - vals[j-1] > 1) {
            qpaw(vals[j] - vals[j-1], N-1);
            for(int i = 0; i < N-1; ++i) {
                for(int k = 0; k <= i; ++k) {
                    f[i][j] += outm[i][k] * f[k][j-1];
                    f[i][j] %= mod;
                }
            }
        } else {
            for(int i = 0; i < N-1; ++i) {
                for(int k = 0; k <= i; ++k) {
                    f[i][j] += inm[i][k] * f[k][j-1];
                    f[i][j] %= mod;
                }
            }
        }
    }
    ll res = 0;
    for(int j = 0; j < vcnt; ++j) {
        for(int i = 0; i < N-1; ++i) {
            if(has[i][j]) {
                res += f[i][j];
                res %= mod;
            }
        }
    }
    printf("%lld %lld\n", maxd + 1, res);
}
### Prompt

Create a solution in cpp for 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 <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <deque>
#include <ctype.h>
#include <limits.h>
#include <map>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>

using namespace std;
typedef long long ll;

void solve();

void init() {
#ifdef _LOCAL_ 
    if(!freopen("case.txt", "r", stdin)) {
        perror("open file failed!:");
        exit(1);
    }
    if(!freopen("main.ans", "w", stdout)) {
        perror("open file failed!:");
        exit(1);
    }
#endif
}


template<class T> T read() {
    int ch = getchar();
    if(ch == EOF) {
        return INT_MIN;
    }
    while(!isdigit(ch) && ch != '-') {
        ch = getchar();
        if(ch == EOF) {
            return INT_MIN;
        }
    }
    T res = 0, sign = 1;
    if(ch == '-') {
        ch = getchar();
        sign = -1;
    }
    while(isdigit(ch)) {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * sign;
}

int main() {
    init();
    solve();
    return 0;
}

/*********************code start here*********************/
const int MAXN = 50;
const ll mod = 998244353;
ll inm[MAXN + 5][MAXN + 5], tmpm[MAXN + 5][MAXN + 5], outm[MAXN + 5][MAXN + 5];
void mul(int n) {
    memset(tmpm, 0, sizeof(tmpm));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = 0; k < n; ++k) {
                tmpm[i][j] += inm[i][k] * inm[k][j];
                tmpm[i][j] %= mod;
            }
        }
    }
    memcpy(inm, tmpm, sizeof(tmpm));
}
void mul2(int n) {
    memset(tmpm, 0, sizeof(tmpm));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = 0; k < n; ++k) {
                tmpm[i][j] += inm[i][k] * outm[k][j];
                tmpm[i][j] %= mod;
            }
        }
    }
    memcpy(outm, tmpm, sizeof(tmpm));
}
void qpaw(ll p, int n) {
    memset(outm, 0, sizeof(outm));
    for(int i = 0; i < n; ++i) {
        outm[i][i] = 1;
    }
    while(p) {
        if(p & 1) {
            mul2(n);
        }
        mul(n);
        p >>= 1;
    }
}

ll arr[MAXN + 5], vals[3*MAXN + 5];
int mini[MAXN + 5], st[MAXN + 5], ed[MAXN + 5], up[MAXN + 5], le[MAXN + 5];
int has[MAXN + 5][3*MAXN + 5];
ll f[MAXN + 5][3*MAXN + 5];

void solve() {
    int n = read<int>(), N = 1, sz = 0;
    arr[0] = 0;
    ll x = read<int>();
    ll pred = 0, cur = 0;
    for(int i = 0; i < n; ++i) {
        ll d = read<int>();
        if(d != 0) {
            if((pred > 0 && d > 0) || (pred < 0 && d < 0)) {
                arr[N-1] += d;
            } else {
                arr[N] = arr[N-1] + d;
                ++N;
            }
            pred = d;
        }
    }
    if(N == 1) {
        printf("1 1\n");
        return;
    }
    if(N == 2 && arr[1] < 0) {
        printf("1 %lld\n", (-arr[1] + 1) % mod);
        return;
    }
    ll minv = 0, maxd = 0;
    for(int i = 0; i < N; ++i) {
        minv = min(minv, arr[i]);
        maxd = max(maxd, arr[i] - minv);
    }
    int vcnt = 0;
    for(int i = 0; i < N; ++i) {
        vals[vcnt++] = arr[i]-1;
        vals[vcnt++] = arr[i];
        vals[vcnt++] = arr[i]+1;
    }
    sort(vals, vals + vcnt);
    vcnt = unique(vals, vals + vcnt) - vals;
    for(int i = 0; i < N; ++i) {
        arr[i] = lower_bound(vals, vals + vcnt, arr[i]) - vals;
    }
    for(int i = 1; i < N; ++i) {
        if(arr[i] > arr[i-1]) {
            st[i-1] = arr[i-1], ed[i-1] = arr[i];
            up[i-1] = 1;
        } else {
            st[i-1] = arr[i] + 1, ed[i-1] = arr[i-1] - 1;
            up[i-1] = 0;
        }
    }
    memset(f, 0, sizeof(f));
    memset(le, 0x3f, sizeof(le));
    for(int i = 0; i < N-1; ++i) {
        for(int j = 0; j <= i; ++j) {
            if(vals[ed[i]] - vals[st[j]] == maxd) {
                f[j][st[j]] = 1;
                has[i][ed[i]] = 1;
                for(int k = j; k <= i; ++k) {
                    le[k] = min(le[k], j);
                }
            }
        }
    }
    for(int j = 1; j < vcnt; ++j) {
        memset(inm, 0, sizeof(inm));
        for(int i = 0, mini = 0; i < N-1; ++i) {
            if(st[i] < st[mini]) {
                mini = i;
            }
            if(st[i] <= j && j <= ed[i]) {
                for(int k = i-1; k >= le[i]; --k) {
                    if(st[k] <= j-1 && ed[k] >= j-1) {
                        inm[i][k] = 1;
                    }
                }
                if(up[i] && st[i] <= j-1) {
                    inm[i][i] = 1;
                }
            }
        }
        if(vals[j] - vals[j-1] > 1) {
            qpaw(vals[j] - vals[j-1], N-1);
            for(int i = 0; i < N-1; ++i) {
                for(int k = 0; k <= i; ++k) {
                    f[i][j] += outm[i][k] * f[k][j-1];
                    f[i][j] %= mod;
                }
            }
        } else {
            for(int i = 0; i < N-1; ++i) {
                for(int k = 0; k <= i; ++k) {
                    f[i][j] += inm[i][k] * f[k][j-1];
                    f[i][j] %= mod;
                }
            }
        }
    }
    ll res = 0;
    for(int j = 0; j < vcnt; ++j) {
        for(int i = 0; i < N-1; ++i) {
            if(has[i][j]) {
                res += f[i][j];
                res %= mod;
            }
        }
    }
    printf("%lld %lld\n", maxd + 1, res);
}
```