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:
#define _CRT_SECURE_NO_WARNINGS
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <array>
#include <vector>
#include <algorithm>

typedef long long lint;
const lint mod(998244353);
class matrix {
public:
	matrix() { cx = cy = 0; memset(val, 0, sizeof(val)); }
	matrix operator*(const matrix& m) const {
		matrix ret;
		if (cy != m.cx) throw "????";
		ret.cx = cx, ret.cy = m.cy;
		for (int i(0); i != cx; ++i) {
			for (int j(0); j != m.cy; ++j) {
				for (int k(0); k != cy; ++k) {
					ret.val[i][j] = (ret.val[i][j] + val[i][k] * m.val[k][j] % mod) % mod;
				}
			}
		}
		return ret;
	}
	lint val[61][61];
	int cx, cy;
};
int n, x, sz;
lint ans, ans2, all[61], hash[61];
bool inc[61];
matrix base, mul;
bool inrange(int pos, int n, lint val) {//val为原值
	if (pos + 1 == n) {
		if (inc[pos]) return val >= hash[all[pos]] && val <= hash[all[pos + 1]];
		return val >= hash[all[pos + 1]] && val <= hash[all[pos]];
	}
	if (inc[pos]) return val >= hash[all[pos]] && val < hash[all[pos + 1]];
	return val > hash[all[pos + 1]] && val <= hash[all[pos]];
}
matrix power(matrix val, lint n) {
	matrix ret;
	ret.cx = ret.cy = val.cy;
	for (int i(0); i != ret.cx; ++i) ret.val[i][i] = 1;
	while (n) {
		if (n & 1) ret = ret * val;
		val = val * val;
		n >>= 1;
	} return ret;
}
void init_mul(int l, int r, lint begin) {
	mul.cx = mul.cy = r - l;
	memset(mul.val, 0, sizeof(mul.val));
	for (int i(l); i < r; ++i) {
		if (inrange(i, r, begin)) {
			for (int j(0); j != i - l; ++j) {
				mul.val[j][i - l] = 1;
			}
			if (inc[i]) mul.val[i - l][i - l] = 1;
		}
	}
}
int main() {
	scanf("%d%d", &n, &x);
	for (int i(1); i <= n; ++i) {
		scanf("%lld", &all[i]);
		if (all[i] == 0) {
			--i, --n;
			continue;
		}
	}
	for (int i(2); i <= n; ++i) {
		if ((all[i - 1] > 0 && all[i] > 0) || (all[i - 1] < 0 && all[i] < 0)) {
			all[i - 1] += all[i];
			for (int j(i + 1); j <= n; ++j) all[j - 1] = all[j];
			--n, --i;
		}
	}
	for (int i(1); i <= n; ++i) {
		all[i] += all[i - 1];
		hash[i] = all[i];
	}
	if (n == 0) {
		printf("1 1\n");
		return 0;
	}
	if (n == 1) {
		if (all[1] < 0) printf("1 %lld\n", (-all[1] % mod + 1) % mod);
		else printf("%lld 1\n", all[1] + 1);
		return 0;
	}
	for (int i(1); i <= n; ++i) {
		for (int j(0); j < i; ++j) {
			if (all[i] - all[j] > ans) ans = all[i] - all[j];
		}
	}
	std::sort(hash, hash + n + 1);
	sz = std::unique(hash, hash + n + 1) - hash;
	for (int i(0); i <= n; ++i) {
		all[i] = std::lower_bound(hash, hash + sz, all[i]) - hash;
	}
	for (int i(0); i != n; ++i) {
		if (all[i + 1] > all[i]) inc[i] = true;
	}
	for (int i(0); i < n; ) {//  [, )
		int next(n);
		while (next > i && hash[all[next]] - hash[all[i]] != ans) --next;
		if (next <= i) {
			++i;
			continue;
		}
		memset(base.val, 0, sizeof(base.val));
		int size(next - i);
		base.cx = 1, base.cy = size;
		for (int j(i); j < next; ++j) {
			if (all[j] == all[i]) base.val[0][j - i] = 1;
		}
		init_mul(i, next, hash[all[i]] + 1);
		int l(all[i]);
		while (l != all[next]) {
			base = base * power(mul, hash[l + 1] - hash[l] - 1);
			++l;
			init_mul(i, next, hash[l]);
			base = base * mul;
			init_mul(i, next, hash[l] + 1);
		}
		for (int j(i); j < next; ++j) {
			ans2 = (ans2 + base.val[0][j - i]) % mod;
		}
		i = next + 1;
	}
	printf("%lld %lld\n", ans + 1, ans2);
	return 0;
}