#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < int(n); i++) 
using namespace std;const int MOD = 998244353;const int N = 51;int add(int a, int b){a += b;if (a >= MOD)a -= MOD;if (a < 0)a += MOD;return a;}
int mul(int a, int b){return a * 1ll * b % MOD;}struct seg{int l, r;};struct segll{long long l, r;};typedef array<array<int, N>, N> mat;
mat operator *(const mat &a, const mat &b){mat c;forn(i, N) forn(j, N) c[i][j] = 0;forn(i, N) forn(j, N) forn(k, N) c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));return c;}
mat binpow(mat a, int b){mat res;forn(i, N) forn(j, N) res[i][j] = i == j;while (b){if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;}
int solve(const vector<int> &a){
	int n = a.size();
	vector<segll> segs;
	long long x = 0;
	forn(i, n){
		segs.push_back({x + (a[i] < 0 ? -1 : 1), x + a[i]});
		x += a[i];
	}
	segs[0].l = 0;
	vector<long long> qs;
	for (auto it : segs){
		qs.push_back(it.l - 1);
		qs.push_back(it.l);
		qs.push_back(it.l + 1);
		qs.push_back(it.r - 1);
		qs.push_back(it.r);
		qs.push_back(it.r + 1);
	}
	sort(qs.begin(), qs.end());
	qs.resize(unique(qs.begin(), qs.end()) - qs.begin());
	qs.pop_back();
	vector<int> ans(n + 1);
	ans[0] = 1;
	long long lst = -1;
	for (auto x : qs){
		mat cur;
		forn(i, N) forn(j, N) cur[i][j] = 0;
		forn(i, n) if (min(segs[i].l, segs[i].r) <= lst + 1 && x <= max(segs[i].l, segs[i].r)){
			if (segs[i].l < segs[i].r)
				forn(j, i + 2) cur[j][i + 1] = 1;
			else
				forn(j, i + 1) cur[j][i + 1] = 1;
		}
		cur = binpow(cur, x - lst);
		vector<int> nans(n + 1);
		forn(i, n + 1) forn(j, n + 1)
			nans[j] = add(nans[j], mul(ans[i], cur[i][j]));
		ans = nans;
		lst = x;
	}
	int sum = 0;
	forn(i, n + 1) sum = add(sum, ans[i]);
	return sum;
}

int main(){int n;scanf("%d", &n);int x;scanf("%d", &x);vector<int> a;forn(i, n){int x;scanf("%d", &x);if (x != 0)a.push_back(x);}n = a.size();vector<seg> d;long long mx = 0;
	forn(i, n){long long cur = 0;for (int j = i; j < n; ++j){cur += a[j];mx = max(mx, cur);}}
	if (mx == 0){
		int sum = 1;
		forn(i, n) sum = add(sum, -a[i]);
		printf("1 %d\n", sum);
		return 0;
	}
	vector<seg> bst;
	forn(i, n){
		long long cur = 0;
		int r = -1;
		for (int j = i; j < n; ++j){
			cur += a[j];
			if (mx == cur) r = j;
		}
		if (r != -1){
			bst.push_back({i, r});
			i = r;
		}
	}
	int sum = 0;
	for (auto it : bst) sum = add(sum, solve(vector<int>(a.begin() + it.l, a.begin() + it.r + 1)));
	printf("%lld %d\n", mx + 1, sum);
}
### 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 <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < int(n); i++) 
using namespace std;const int MOD = 998244353;const int N = 51;int add(int a, int b){a += b;if (a >= MOD)a -= MOD;if (a < 0)a += MOD;return a;}
int mul(int a, int b){return a * 1ll * b % MOD;}struct seg{int l, r;};struct segll{long long l, r;};typedef array<array<int, N>, N> mat;
mat operator *(const mat &a, const mat &b){mat c;forn(i, N) forn(j, N) c[i][j] = 0;forn(i, N) forn(j, N) forn(k, N) c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));return c;}
mat binpow(mat a, int b){mat res;forn(i, N) forn(j, N) res[i][j] = i == j;while (b){if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;}
int solve(const vector<int> &a){
	int n = a.size();
	vector<segll> segs;
	long long x = 0;
	forn(i, n){
		segs.push_back({x + (a[i] < 0 ? -1 : 1), x + a[i]});
		x += a[i];
	}
	segs[0].l = 0;
	vector<long long> qs;
	for (auto it : segs){
		qs.push_back(it.l - 1);
		qs.push_back(it.l);
		qs.push_back(it.l + 1);
		qs.push_back(it.r - 1);
		qs.push_back(it.r);
		qs.push_back(it.r + 1);
	}
	sort(qs.begin(), qs.end());
	qs.resize(unique(qs.begin(), qs.end()) - qs.begin());
	qs.pop_back();
	vector<int> ans(n + 1);
	ans[0] = 1;
	long long lst = -1;
	for (auto x : qs){
		mat cur;
		forn(i, N) forn(j, N) cur[i][j] = 0;
		forn(i, n) if (min(segs[i].l, segs[i].r) <= lst + 1 && x <= max(segs[i].l, segs[i].r)){
			if (segs[i].l < segs[i].r)
				forn(j, i + 2) cur[j][i + 1] = 1;
			else
				forn(j, i + 1) cur[j][i + 1] = 1;
		}
		cur = binpow(cur, x - lst);
		vector<int> nans(n + 1);
		forn(i, n + 1) forn(j, n + 1)
			nans[j] = add(nans[j], mul(ans[i], cur[i][j]));
		ans = nans;
		lst = x;
	}
	int sum = 0;
	forn(i, n + 1) sum = add(sum, ans[i]);
	return sum;
}

int main(){int n;scanf("%d", &n);int x;scanf("%d", &x);vector<int> a;forn(i, n){int x;scanf("%d", &x);if (x != 0)a.push_back(x);}n = a.size();vector<seg> d;long long mx = 0;
	forn(i, n){long long cur = 0;for (int j = i; j < n; ++j){cur += a[j];mx = max(mx, cur);}}
	if (mx == 0){
		int sum = 1;
		forn(i, n) sum = add(sum, -a[i]);
		printf("1 %d\n", sum);
		return 0;
	}
	vector<seg> bst;
	forn(i, n){
		long long cur = 0;
		int r = -1;
		for (int j = i; j < n; ++j){
			cur += a[j];
			if (mx == cur) r = j;
		}
		if (r != -1){
			bst.push_back({i, r});
			i = r;
		}
	}
	int sum = 0;
	for (auto it : bst) sum = add(sum, solve(vector<int>(a.begin() + it.l, a.begin() + it.r + 1)));
	printf("%lld %d\n", mx + 1, sum);
}
```