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;
const int N=55,mod=998244353;
typedef long long ll;
#define fi first
#define se second
int n,m,x,a[N],l;
ll ans;
inline void add(int &x,int y){
	x+=y;if(x>=mod) x-=mod;
}
struct Mat{
	int a[N][N];
	Mat(){memset(a,0,sizeof(a));}
	Mat operator * (const Mat & b){
		Mat c;
		for(int k=0;k<=m;k++)
			for(int i=0;i<=m;i++)
				for(int j=0;j<=m;j++)
					add(c.a[i][j],1ll*a[i][k]*b.a[k][j]%mod);
		return c;
	}
};
vector<pair<ll,ll>> seg;
vector<ll> d;
Mat qpow(Mat a,int b){
	Mat res;
	for(int i=0;i<=m;i++) res.a[i][i]=1;
	for(;b;b>>=1,a=a*a) if(b&1) res=res*a;
	return res;
}
int solve(int l,int r){
	m=r-l+1;ll s=0;
	seg.clear(),d.clear();
	for(int i=l;i<=r;i++){
		seg.emplace_back(s+(a[i]<0?-1:1),s+a[i]);
		s+=a[i];
	}
	seg[0].fi=0;
	for(int i=0;i<seg.size();i++){
		d.push_back(seg[i].fi-1);
		d.push_back(seg[i].fi);
		d.push_back(seg[i].fi+1);
		d.push_back(seg[i].se-1);
		d.push_back(seg[i].se);
		d.push_back(seg[i].se+1);
	}	
	sort(d.begin(),d.end());
	d.erase(unique(d.begin(),d.end()),d.end());d.pop_back();
	Mat ans;ans.a[0][0]=1;
	ll la=-1;
	for(int i=0;i<d.size();i++){
		Mat t;
		for(int j=0;j<seg.size();j++){
			if(min(seg[j].fi,seg[j].se)<=la+1&&max(seg[j].fi,seg[j].se)>=d[i]){
				if(seg[j].fi<seg[j].se) {
					for(int k=0;k<=j;k++) t.a[k][j]=1;
				}else {
					for(int k=0;k<j;k++) t.a[k][j]=1;
				}
			}
		}
		t=qpow(t,d[i]-la);
		ans=ans*t;
		la=d[i];
	}
	int res=0;
	for(int i=0;i<=m;i++) add(res,ans.a[0][i]);
	return res;
}
int main(){
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(x) a[++l]=x;
	}
	n=l;
	ll sum=0;
	for(int i=1;i<=n;i++){
		ll t=sum;
		for(int j=i;j<=n;j++){
			t+=a[j];
			ans=max(ans,t-sum);
		}
		sum+=a[i];
	}
	if(ans==0){
		ll res=1;
		for(int i=1;i<=n;i++) res-=a[i];
		printf("%lld %lld",ans+1,res%mod);
		return 0;
	}
	sum=0;int res=0;
	for(int i=1;i<=n;i++){
		ll t=sum;int p=-1;
		for(int j=i;j<=n;j++){
			t+=a[j];
			if(t-sum==ans) p=j;
		}
		sum+=a[i];
		if(p!=-1){
			//cout<<i<<' '<<p<<endl;
			add(res,solve(i,p));
			i=p;
		}
	}
	printf("%lld %d",ans+1,res);
	return 0;
}