#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j), i##E = k; i <= i##E; i++) 
#define R(i, j, k) for(int i = (j), i##E = k; i >= i##E; i--)
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define db double
#define sz(a) a.size()
#define x first
#define y second
#define vi vector<int>
using namespace std;
const int N = 1e4, M = 100, mod = 998244353;
int m;
struct Matrix {
	int f[M][M];
	Matrix (int x = 1) {
		L(i, 1, m) L(j, 1, m) f[i][j] = (i == j ? x : 0);
	}
} ;
Matrix operator * (Matrix aa, Matrix bb) {
	Matrix res(0);
	L(i, 1, m) L(j, 1, m) L(k, 1, m) (res.f[i][j] += (ll) aa.f[i][k] * bb.f[k][j] % mod) %= mod;
	return res;
}
Matrix operator ^ (Matrix x, ll y) {
	Matrix res(1);
	for(; y; x = x * x, y >>= 1) if(y & 1) res = res * x;
	return res;
}

int n, nousex, otp, s[N], tot, v[N], sv[N], ns;
ll a[N], p[N], mx, val, arr[N], sl[N], sr[N];
void calc(int l, int r) {
	ll mx = 0;
	p[l] = 0, tot = 0;
	L(i, l + 1, r) {
		sl[i] = (p[i - 1] + (a[i] < 0 ? -1 : 1)), p[i] = p[i - 1] + a[i], sr[i] = p[i];
		if(sl[i] > sr[i]) swap(sl[i], sr[i]);
		mx = max(mx, p[i]);	
	}
	if(val != mx) return;
	sl[l + 1] = 0;
	L(i, l + 1, r) 
		arr[++tot] = sl[i] - 1, arr[++tot] = sl[i], arr[++tot] = sl[i] + 1, 
		arr[++tot] = sr[i] - 1, arr[++tot] = sr[i], arr[++tot] = sr[i] + 1;
	sort(arr + 1, arr + tot + 1), tot = unique(arr + 1, arr + tot + 1) - arr - 1;
	m = r - l;
	memset(v, 0, sizeof(v));
	v[1] = 1, arr[0] = -1;
	L(k, 1, tot) if(arr[k] <= mx) {
		Matrix G(0);
		L(i, l + 1, r) if(sl[i] <= arr[k - 1] + 1 && arr[k] <= sr[i]) {
			L(j, l + 1, i - 1) G.f[j - l][i - l] = 1;
			if(a[i] > 0) G.f[i - l][i - l] = 1;
		}
		G = G ^ (arr[k] - arr[k - 1]);
		L(i, 1, m) L(j, 1, m) (sv[j] += (ll) v[i] * G.f[i][j] % mod) %= mod;
		L(i, 1, m) v[i] = sv[i], sv[i] = 0;
	}
	L(i, 1, m) (ns += v[i]) %= mod;
}
void Main() {
	cin >> n >> nousex;
	L(i, 1, n) {
		cin >> a[i];
		if(a[i]) a[++otp] = a[i];
	}
	n = otp, otp = 0;
	L(i, 1, n) 
		if((a[i] > 0 && a[i - 1] > 0) || (a[i] < 0 && a[i - 1] < 0)) a[otp] += a[i];
		else a[++otp] = a[i];
	n = otp;
	L(i, 1, n) mx += a[i], val = max(val, mx), mx = max(mx, 0ll);
	cout << val + 1 << " ";
	if(val == 0) {
		int sum = 1;
		L(i, 1, n) (sum += abs(a[i]) % mod) %= mod;
		return cout << sum << "\n", void();
	}
	int top = 0;
	mx = 0;
	L(i, 1, n) {
		mx += a[i];
		if(mx < 0) s[++top] = i, mx = 0;
	}
	s[++top] = n + 1;
	L(i, 1, top) calc(s[i - 1], s[i] - 1);
	cout << ns << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	Main();
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 L(i, j, k) for(int i = (j), i##E = k; i <= i##E; i++) 
#define R(i, j, k) for(int i = (j), i##E = k; i >= i##E; i--)
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define db double
#define sz(a) a.size()
#define x first
#define y second
#define vi vector<int>
using namespace std;
const int N = 1e4, M = 100, mod = 998244353;
int m;
struct Matrix {
	int f[M][M];
	Matrix (int x = 1) {
		L(i, 1, m) L(j, 1, m) f[i][j] = (i == j ? x : 0);
	}
} ;
Matrix operator * (Matrix aa, Matrix bb) {
	Matrix res(0);
	L(i, 1, m) L(j, 1, m) L(k, 1, m) (res.f[i][j] += (ll) aa.f[i][k] * bb.f[k][j] % mod) %= mod;
	return res;
}
Matrix operator ^ (Matrix x, ll y) {
	Matrix res(1);
	for(; y; x = x * x, y >>= 1) if(y & 1) res = res * x;
	return res;
}

int n, nousex, otp, s[N], tot, v[N], sv[N], ns;
ll a[N], p[N], mx, val, arr[N], sl[N], sr[N];
void calc(int l, int r) {
	ll mx = 0;
	p[l] = 0, tot = 0;
	L(i, l + 1, r) {
		sl[i] = (p[i - 1] + (a[i] < 0 ? -1 : 1)), p[i] = p[i - 1] + a[i], sr[i] = p[i];
		if(sl[i] > sr[i]) swap(sl[i], sr[i]);
		mx = max(mx, p[i]);	
	}
	if(val != mx) return;
	sl[l + 1] = 0;
	L(i, l + 1, r) 
		arr[++tot] = sl[i] - 1, arr[++tot] = sl[i], arr[++tot] = sl[i] + 1, 
		arr[++tot] = sr[i] - 1, arr[++tot] = sr[i], arr[++tot] = sr[i] + 1;
	sort(arr + 1, arr + tot + 1), tot = unique(arr + 1, arr + tot + 1) - arr - 1;
	m = r - l;
	memset(v, 0, sizeof(v));
	v[1] = 1, arr[0] = -1;
	L(k, 1, tot) if(arr[k] <= mx) {
		Matrix G(0);
		L(i, l + 1, r) if(sl[i] <= arr[k - 1] + 1 && arr[k] <= sr[i]) {
			L(j, l + 1, i - 1) G.f[j - l][i - l] = 1;
			if(a[i] > 0) G.f[i - l][i - l] = 1;
		}
		G = G ^ (arr[k] - arr[k - 1]);
		L(i, 1, m) L(j, 1, m) (sv[j] += (ll) v[i] * G.f[i][j] % mod) %= mod;
		L(i, 1, m) v[i] = sv[i], sv[i] = 0;
	}
	L(i, 1, m) (ns += v[i]) %= mod;
}
void Main() {
	cin >> n >> nousex;
	L(i, 1, n) {
		cin >> a[i];
		if(a[i]) a[++otp] = a[i];
	}
	n = otp, otp = 0;
	L(i, 1, n) 
		if((a[i] > 0 && a[i - 1] > 0) || (a[i] < 0 && a[i - 1] < 0)) a[otp] += a[i];
		else a[++otp] = a[i];
	n = otp;
	L(i, 1, n) mx += a[i], val = max(val, mx), mx = max(mx, 0ll);
	cout << val + 1 << " ";
	if(val == 0) {
		int sum = 1;
		L(i, 1, n) (sum += abs(a[i]) % mod) %= mod;
		return cout << sum << "\n", void();
	}
	int top = 0;
	mx = 0;
	L(i, 1, n) {
		mx += a[i];
		if(mx < 0) s[++top] = i, mx = 0;
	}
	s[++top] = n + 1;
	L(i, 1, top) calc(s[i - 1], s[i] - 1);
	cout << ns << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	Main();
	return 0;
}
```