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>

using namespace std;

#define MOD 998244353
#define MAGIC 55

int n;
long long x, aa = -1, bb;
vector<long long> v, vv, fr, mm, ma;
vector<vector<long long>> ans;
map<long long, int> m;

long long po(long long b, int p) {
	long long re = 1;
	while (p) {
		if (p % 2) re = re * b % MOD;
		b = b * b % MOD;
		p /= 2;
	}
	return re;
}

long long inv(int a) {
	return po(a, MOD - 2);
}

void add(long long& a, long long b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}

void sub(long long& a, long long b) {
	add(a, MOD - b);
}

long long subb(long long a, long long b) {
	sub(a, b);
	return a;
}

long long get(int a, long long b) {
	if (fr[a] == LLONG_MIN) return 0;
	if (b < MAGIC) return ans[a][b];
	long long re = 0;
	ma[MAGIC] = 1;
	b = (b % MOD + MOD) % MOD;
	for (int i = MAGIC - 1; i >= 0; i--)
		ma[i] = ma[i + 1] * subb(b, i) % MOD;
	long long tmp = 1;
	for (int i = 0; i < MAGIC; i++) {
		re = (re + ans[a][i] * mm[i] % MOD * tmp % MOD * ma[i + 1]) % MOD;
		tmp = tmp * subb(b, i) % MOD;
	}
	return re;
}

int main() {
	ma.resize(MAGIC + 1);
	mm.resize(MAGIC);
	for (int i = 0; i < MAGIC; i++) {
		mm[i] = 1;
		for (int j = 0; j < MAGIC; j++)
			if (i != j)
				mm[i] = mm[i] * inv(subb(i, j)) % MOD;
	}
	scanf("%d%lld", &n, &x);
	for (int i = 0; i < n; i++) {
		long long tmp;
		scanf("%lld", &tmp);
		if (tmp == 0) continue;
		if (v.empty() || (tmp > 0) != (v.back() > 0)) v.push_back(tmp);
		else v.back() += tmp;
	}
	long long bku = x;
	m[x] = 0;
	m[x + 1] = 0;
	for (long long i : v) {
		if (i > 0) {
			m[x + 1] = 0;
			m[x + i + 1] = 0;
		} else {
			m[x] = 0;
			m[x + i] = 0;
		}
		x += i;
	}
	x = bku;
	int cnt = 0;
	for (auto& i : m) {
		vv.push_back(i.first);
		i.second = cnt++;
	}
	fr = vector<long long>(cnt - 1, LLONG_MIN);
	ans.resize(cnt - 1);
	for (int i = 0; i < cnt - 1; i++) ans[i].resize(min((long long)MAGIC, vv[i + 1] - vv[i]));
	int tmp = m[x];
	fr[tmp] = x;
	ans[tmp][0] = 1;
	for (long long i : v) {
		if (i > 0) {
			int ta = m[x + 1];
			int tb = m[x + i + 1];
			long long tc = fr[ta - 1] == LLONG_MAX ? x : fr[ta - 1];
			for (int j = ta; j < tb; j++) {
				long long la = get(j - 1, vv[j] - 1 - vv[j - 1]);
				if (fr[j] != tc)
					for (auto& k : ans[j]) k = la;
				else
					for (auto& k : ans[j]) {
						add(k, la);
						la = k;
					}
				fr[j] = tc;
			}
		} else {
			int ta = m[x];
			int tb = m[x + i];
			for (int j = ta - 1; j >= tb; j--)
				if (fr[j] == LLONG_MIN) {
					fr[j] = LLONG_MAX;
					for (auto& k : ans[j]) k = 1;
				} else if (fr[j] == LLONG_MAX)
					for (auto& k : ans[j]) add(k, 1);
				else {
					for (int k = ans[j].size() - 1; k; k--)
						add(ans[j][k], ans[j][k - 1]);
					if (fr[j] == vv[j]) add(ans[j][0], 1);
					else add(ans[j][0], get(j - 1, vv[j] - 1 - vv[j - 1]));
				}
		}
		x += i;
	}
	for (int i = 0; i < cnt - 1; i++) {
		long long aaa, bbb;
		if (fr[i] == LLONG_MAX) {
			aaa = 1;
			bbb = (vv[i + 1] - vv[i]) % MOD;
		} else {
			aaa = vv[i + 1] - fr[i];
			bbb = get(i, vv[i + 1] - 1 - vv[i]);
		}
		if (aaa > aa) {
			aa = aaa;
			bb = bbb;
		} else if (aaa == aa) add(bb, bbb);
	}
	printf("%lld %lld\n", aa, bb);
}