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:
#include<bits/stdc++.h>

#define rep(x, L, R) for(int x = (L), _x = (R); x <= _x; x++)
#define per(x, R, L) for(int x = (R), _x = (L); x >= _x; x--)
#define forgp(u, g, v) for(int iu = 0, v; iu < (int)g[u].size() && (v = g[u][iu], 1); iu++)
#define mp make_pair
#define siz(v) (int)(v).size()
#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;
typedef long long LL;
typedef double db;
const int N = 50 + 10, P = 998244353;
int n;
LL a[N], b[N], p[N];
int dp[N][N], cnt[N][N][N];
int fac[N], ifac[N];
map<LL, int> id;

int qpow(int a, int b) {
	int res = 1;
	for(; b; b >>= 1, a = 1ll * a * a % P) if(b & 1) res = 1ll * res * a % P;
	return res;
}

int C(int n, int m) {
	if(n < m) return 0;
	return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

void initmath(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = qpow(fac[n], P - 2);
	for(int i = n - 1; i >= 0; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	return;
}

int Calc(int b, int e, LL s, LL t) {
	if(s > t) return 1;
	int cnt = 0;
	for(int i = b; i <= e; i++) {
		if(a[i - 1] > a[i]) continue;
		if(a[i - 1] <= s && t <= a[i]) {
			cnt++;
		}
	}
	if(cnt <= 0) return 0;
	int res = 0;
	for(int i = 0; i <= cnt - 1 && i <= t - s + 1; i++) {
		int und = 1;
		for(int j = 0; j < cnt - 1; j++) und = 1ll * und * ((t - s - i + cnt - j) % P + P) % P;
		und = 1ll * und * ifac[cnt - 1] % P;
		res = (res + 1ll * und * C(cnt - 1, i) % P) % P;
	}
	return res;
}

int main() {
	scanf("%d", &n);
	initmath(n);
	scanf("%lld", &a[0]);
	int tot = 0;
	for(int i = 1; i <= n; i++) {
		LL d;
		scanf("%lld", &d);
		if(d) a[tot + 1] = a[tot] + d, tot++;
	}
	n = tot;
	memcpy(b, a, sizeof(a));
	sort(b, b + n + 1);
	tot = -1;
	for(int i = 0; i <= n; i++) {
		if(id.find(b[i]) == id.end()) {
			id[b[i]] = ++tot;
			b[tot] = b[i];
		}
	}
	for(int i = 0; i <= n; i++) p[i] = id[a[i]];
	LL mx = 0;
	for(int i = 0; i <= n; i++) {
		LL und = a[i];
		for(int j = i; j <= n; j++) und = max(und, a[j]);
		mx = max(mx, und - a[i] + 1);
	}
	if(mx == 1) return printf("%lld %lld\n", mx, (b[tot] - b[0] + 1) % P), 0;
	for(int i = 0; i < tot; i++) for(int j = 1; j <= n; j++) for(int k = j; k <= n; k++) {
		cnt[i][j][k] = Calc(j, k, b[i] + 1, b[i + 1] - 1);
	}
	int res = 0;
	for(int str = 0; str <= n; str++) {
		memset(dp, 0, sizeof(dp));
		if(str && a[str] > a[str - 1]) continue;
		if(str < n && a[str + 1] < a[str]) continue;
		dp[p[str]][str + 1] = 1;
		for(int i = p[str]; i < tot; i++) {
			for(int j = str + 1; j <= n; j++) {
				for(int k = j + (a[j - 1] > a[j]); k <= n; k++) {
					LL L = a[k - 1], R = a[k];
					if(L > R) L--;
					else L++;
					if(L > R) swap(L, R);
					if(b[i + 1] < L || R < b[i + 1]) continue;
					(dp[i + 1][k] += 1ll * dp[i][j] * cnt[i][j][k] % P) %= P;
				}
			}
		}
		for(int i = str; i <= n; i++) {
			if(a[i] - a[str] + 1 == mx) {
				(res += dp[p[i]][i]) %= P;
			}
		}
	}
	printf("%lld %d\n", mx, res);
	return 0;
}