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;
typedef long long ll;
 
const int maxn = 101;
const int M = 998244353;
 
int n, m;
int d[maxn];
ll a[maxn * 10], ans = 0, res = 0;
 
struct Mat{
	ll a[maxn][maxn];
	
	Mat(){ memset(a, 0, sizeof(a)); }
	
	void build(){
		for(int i = 0 ; i <= m ; ++i){
			a[i][i] = 1;
		}
	}
	
	Mat operator * (const Mat & B) const{
		Mat res;
		ll r;
		for(int i = 0 ; i <= m ; ++i){
			for(int k = 0 ; k <= m ; ++k){
				r = a[i][k];
				for(int j = 0 ; j <= m ; ++j){
					res.a[i][j] += 1ll * r * B.a[k][j] % M;
					res.a[i][j] %= M;
				}	
			}
		}
		return res;
	}
};
 
struct SEG{
	ll l, r;
}seg[maxn];
 
Mat qsm(Mat base, ll po){
	Mat an; an.build();
	while(po){
		if(po & 1) an = an * base;
		po >>= 1;
		base = base * base;
	}
	return an;
}
 
int solve(int l, int r){
//	printf("%d %d\n", l, r);
	m = r - l + 1;
	
	int seg_n = 0, val_n = 0;
	
	ll sum = 0;
	for(int i = l ; i <= r ; ++i){
		++seg_n;
		seg[seg_n].l = sum + (d[i] < 0 ? -1 : 1);
		seg[seg_n].r = sum + d[i];
		sum += d[i];
	}
	seg[1].l = 0;
	
	for(int i = 1 ; i <= seg_n ; ++i){
		a[++val_n] = seg[i].l;
//		a[++val_n] = seg[i].l - 1;
//		a[++val_n] = seg[i].l + 1;
		a[++val_n] = seg[i].r;
		a[++val_n] = seg[i].r - 1;
//		a[++val_n] = seg[i].r + 1;
	}
	
//	a[++val_n] = -1;
//	a[++val_n] = 1;
	sort(a + 1, a + 1 + val_n);
	val_n = unique(a + 1, a + 1 + val_n) - a - 1;
//
	
//	printf("%d\n", val_n);
//	for(int i = 1 ; i <= val_n ; ++i) printf("%lld " , a[i]); printf("\n");
	
	Mat val;
	val.a[0][0] = 1;
	ll lst = -1;
	for(int i = 1 ; i <= val_n ; ++i){
		Mat base;
		for(int j = 1 ; j <= seg_n ; ++j){
			if(min(seg[j].l, seg[j].r) <= lst + 1 && max(seg[j].l, seg[j].r) >= a[i]){
				if(seg[j].l < seg[j].r){
					for(int k = 0 ; k <= j ; ++k){
						base.a[k][j] = 1;
					} 
				} else{
					for(int k = 0 ; k < j ; ++k){
						base.a[k][j] = 1;
					}
				}
			}
		}
		base = qsm(base, a[i] - lst);
		val = val * base;
		lst = a[i];
	}
	
	int tot = 0;
	for(int i = 0 ; i <= m ; ++i){
		tot += val.a[0][i];
		tot %= M;
	}
	return tot;
}
 
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
 
int main(){
	scanf("%d", &n); 
	ll x;
	ll sum;
	scanf("%d", &x);
	int cnt = 0;
	for(int i = 1 ; i <= n ; ++i){
		scanf("%lld", &x);
		if(x != 0){
			d[++cnt] = x;
		}
	}
	
	n = cnt;
	
	x = sum = 0;
	for(int i = 1 ; i <= n ; ++i){
		ll tmp = sum;
		for(int j = i ; j <= n ; ++j){
			tmp += d[j];
			ans = max(ans, tmp - sum);
		}
		sum += d[i];
	}
	
//	printf("%lld\n", ans + 1);
	if(ans == 0){
		int val = 1;
		for(int i = 1 ; i <= n ; ++i){
			val = (val - d[i]) % M;
		}
		printf("%lld %d\n", ans + 1, val);
		return 0;
	}
 
	sum = 0;
	
	for(int i = 1 ; i <= n ; ++i){
		ll tmp = sum;
		int right = -1;
		for(int j = i ; j <= n ; ++j){
			tmp += d[j];
			if(tmp - sum == ans){
				right = j;		
			}
		}
		sum += d[i];
		if(right != -1){
			res += solve(i, right); 
			res %= M;
			sum = 0;
			i = right;
		}
	}
	
	printf("%lld %d\n", ans + 1, res);
	
	return 0;
}