#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 51;
const int M = 998244353;
 
int n;
int d[maxn+5];
int m;

struct Matrix{
	int a[maxn+5][maxn+5];
	void init_zero(){
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				a[i][j]=0;
			}
		}
	}
	void init(){
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				a[i][j]=(i==j);
			}
		}
	}
	friend Matrix operator *(Matrix a,Matrix b){
		Matrix ans;
		ans.init_zero();
		for(int i=0;i<=m;i++){
			for(int k=0;k<=m;k++){
				for(int j=0;j<=m;j++){
					ans.a[i][j]=(ans.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%M;
				}
			}
		}
		return ans;
	}
};
 
//struct Mat{
//	ll a[maxn][maxn];
//	
//	Mat(){ 
//		for(int i=0;i<=m;i++){
//			for(int j=0;j<=m;j++){
//				a[i][j]=0;
//			}
//		}
//	}
//	
//	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 Vector{
	int a[maxn+5];
//	Vector(){
//		for(int i=0;i<=m;i++){
//			a[i]=0;
//		}
//	}
	void init_zero(){
		for(int i=0;i<=m;i++){
			a[i]=0;
		}
	}
	friend Vector operator *(Vector a, Matrix b){
		Vector ans;
		ans.init_zero();
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				ans.a[j]=(ans.a[j]+1ll*a.a[i]*b.a[i][j])%M;
			}
		}
		return ans;
	}
};
 

 
Matrix quick_power(Matrix a,int b){
	Matrix ans;
	ans.init();
	while(b){
		if(b&1){
			ans=ans*a;
		}
		b>>=1;
		a=a*a;
	}
	return ans;
}
struct Segment{
	ll l,r;
}seg[maxn+5];
int seg_len;
ll a[maxn*6+5];
int a_len;
int solve(int l,int r){
	m=r-l+1;
	seg_len=0;
	ll x=0;
	for(int i=l;i<=r;i++){
		seg_len++;
		seg[seg_len].l=(x+(d[i]<0?-1:1));
		seg[seg_len].r=x+d[i];
		x+=d[i];
	}
	seg[1].l=0;
	a_len=0;
	for(int i=1;i<=seg_len;i++){
		a[++a_len]=seg[i].l-1;
		a[++a_len]=seg[i].l;
		a[++a_len]=seg[i].l+1;
		a[++a_len]=seg[i].r-1;
		a[++a_len]=seg[i].r;
		a[++a_len]=seg[i].r+1;
	}
	sort(a+1,a+1+a_len);
	a_len=unique(a+1,a+1+a_len)-a-1;
	a_len--;
	
	Vector ans;
	ans.init_zero();
	ans.a[0]=1;
	ll lst=-1;
	for(int i=1;i<=a_len;i++){
		Matrix tmp;
		tmp.init_zero();
		for(int j=1;j<=seg_len;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++){
						tmp.a[k][j]=1;
					}
				}
				else{
					for(int k=0;k<j;k++){
						tmp.a[k][j]=1;
					}
				}
			}
		}
		tmp=quick_power(tmp,a[i]-lst);
		ans=ans*tmp;
		lst=a[i];
	}
//	for(int i = 1 ; i <= a_len ; ++i) printf("%lld ", a[i]); printf("\n");
	int sum=0;
	for(int i=0;i<=m;i++){
		sum=(sum+ans.a[i])%M;
	}
	return sum;
}

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%*d",&n);
	int cnt = 0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x!=0){
			d[++cnt]=x;
		}
	}
	n=cnt;
	ll ans=0;
	ll 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];
	}
//	scanf("%d", &n); 
//	ll x;
//	ll sum;
//	scanf("%lld", &x);
//	int cnt = 0;
//	for(int i = 1 ; i <= n ; ++i){
//		int y; 
//		scanf("%d", &y);
//		if(y != 0){
//			d[++cnt] = y;
//		}
//	}
//	
//	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;
	int val=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){
			val=(val+solve(i,right))%M;
			i=right;
		}
	}
 
//	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, val);
	
	return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
using namespace std;
typedef long long ll;
 
const int maxn = 51;
const int M = 998244353;
 
int n;
int d[maxn+5];
int m;

struct Matrix{
	int a[maxn+5][maxn+5];
	void init_zero(){
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				a[i][j]=0;
			}
		}
	}
	void init(){
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				a[i][j]=(i==j);
			}
		}
	}
	friend Matrix operator *(Matrix a,Matrix b){
		Matrix ans;
		ans.init_zero();
		for(int i=0;i<=m;i++){
			for(int k=0;k<=m;k++){
				for(int j=0;j<=m;j++){
					ans.a[i][j]=(ans.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%M;
				}
			}
		}
		return ans;
	}
};
 
//struct Mat{
//	ll a[maxn][maxn];
//	
//	Mat(){ 
//		for(int i=0;i<=m;i++){
//			for(int j=0;j<=m;j++){
//				a[i][j]=0;
//			}
//		}
//	}
//	
//	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 Vector{
	int a[maxn+5];
//	Vector(){
//		for(int i=0;i<=m;i++){
//			a[i]=0;
//		}
//	}
	void init_zero(){
		for(int i=0;i<=m;i++){
			a[i]=0;
		}
	}
	friend Vector operator *(Vector a, Matrix b){
		Vector ans;
		ans.init_zero();
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				ans.a[j]=(ans.a[j]+1ll*a.a[i]*b.a[i][j])%M;
			}
		}
		return ans;
	}
};
 

 
Matrix quick_power(Matrix a,int b){
	Matrix ans;
	ans.init();
	while(b){
		if(b&1){
			ans=ans*a;
		}
		b>>=1;
		a=a*a;
	}
	return ans;
}
struct Segment{
	ll l,r;
}seg[maxn+5];
int seg_len;
ll a[maxn*6+5];
int a_len;
int solve(int l,int r){
	m=r-l+1;
	seg_len=0;
	ll x=0;
	for(int i=l;i<=r;i++){
		seg_len++;
		seg[seg_len].l=(x+(d[i]<0?-1:1));
		seg[seg_len].r=x+d[i];
		x+=d[i];
	}
	seg[1].l=0;
	a_len=0;
	for(int i=1;i<=seg_len;i++){
		a[++a_len]=seg[i].l-1;
		a[++a_len]=seg[i].l;
		a[++a_len]=seg[i].l+1;
		a[++a_len]=seg[i].r-1;
		a[++a_len]=seg[i].r;
		a[++a_len]=seg[i].r+1;
	}
	sort(a+1,a+1+a_len);
	a_len=unique(a+1,a+1+a_len)-a-1;
	a_len--;
	
	Vector ans;
	ans.init_zero();
	ans.a[0]=1;
	ll lst=-1;
	for(int i=1;i<=a_len;i++){
		Matrix tmp;
		tmp.init_zero();
		for(int j=1;j<=seg_len;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++){
						tmp.a[k][j]=1;
					}
				}
				else{
					for(int k=0;k<j;k++){
						tmp.a[k][j]=1;
					}
				}
			}
		}
		tmp=quick_power(tmp,a[i]-lst);
		ans=ans*tmp;
		lst=a[i];
	}
//	for(int i = 1 ; i <= a_len ; ++i) printf("%lld ", a[i]); printf("\n");
	int sum=0;
	for(int i=0;i<=m;i++){
		sum=(sum+ans.a[i])%M;
	}
	return sum;
}

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%*d",&n);
	int cnt = 0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x!=0){
			d[++cnt]=x;
		}
	}
	n=cnt;
	ll ans=0;
	ll 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];
	}
//	scanf("%d", &n); 
//	ll x;
//	ll sum;
//	scanf("%lld", &x);
//	int cnt = 0;
//	for(int i = 1 ; i <= n ; ++i){
//		int y; 
//		scanf("%d", &y);
//		if(y != 0){
//			d[++cnt] = y;
//		}
//	}
//	
//	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;
	int val=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){
			val=(val+solve(i,right))%M;
			i=right;
		}
	}
 
//	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, val);
	
	return 0;
}
```