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;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int mod=998244353;
int n,ans;
ll LIS;
vector<ll> a,peaks;
int sgn(ll x) {
	if (x<0) return -1;
	if (x>0) return 1;
	return 0;
}
void update(int &x,int y) {
	x+=y; if (x>=mod) x-=mod;
}
int D(int i,int j,vector<int> &res) {
	if (i%2==0) return res[j-i];
	if (j-i-1>=0) return res[j-i-1];
	return 0;
}
vector<int> ksm(int cnt,ll d) {
	if (d==1) return vector<int>(cnt,1);
	vector<int> res=ksm(cnt,d/2);
	vector<int> dp(cnt),dp2(cnt);
	for (int j=0;j<cnt;j++)
	for (int i=0;i<=j;i++) {
		update(dp[j],(ll)D(0,i,res)*D(i,j,res)%mod);
	}
	if (d&1) {
		for (int j=0;j<cnt;j++)
		for (int i=0;i<=j;i++)
			if (i<j||j%2==0)
				update(dp2[j],dp[i]);
		return dp2;
	}
	return dp;
}
vector<ll> L,R;
vector<int> flag,dp;
void trans(ll x) {
	vector<int> dp2; dp2.resize(dp.size());
	for (int i=0;i<dp.size();i++)
	for (int j=0;j<i+(flag[i]==1);j++)
		if (L[i]<=x&&x<=R[i]&&L[j]<=x-1&&x-1<=R[j])
			update(dp2[i],dp[j]);
	dp=dp2;
}
void solve(vector<ll> b) {
	vector<ll> c=b;
	sort(c.begin(),c.end());
	int sz=(int)b.size()-1;
	//for (int i=0;i<sz;i++) printf("%lld ",b[i]); printf("\n");
	L.resize(sz),R.resize(sz),flag.resize(sz),dp.resize(sz);
	for (int i=0;i<sz;i++) {
		L[i]=b[i],R[i]=b[i+1];
		if (i!=0) {
			if (L[i]<R[i]) L[i]++; else L[i]--;
		}
		if (L[i]>R[i]) swap(L[i],R[i]),flag[i]=-1;
		else flag[i]=1;
	}
	for (int i=0;i<sz;i++)
		if (L[i]<=c[0]&&c[0]<=R[i]) dp[i]=1;
	ll lst=c[0],z;
	int cnt; vector<int> id(sz);
	for (ll x : c) {
		z=x-2;
		if (lst<z) {
			vector<int> mk(sz);
			for (int i=0;i<sz;i++)
			for (int j=0;j<i+(flag[i]==1);j++)
				if (L[i]<=z&&z<=R[i]&&L[j]<=z&&z<=R[j]) mk[i]=mk[j]=1;
			cnt=0;
			for (int i=0;i<sz;i++) if (mk[i]) id[i]=cnt++;
			vector<int> res=ksm(cnt,z-lst);
			vector<int> dp2(sz);
			for (int i=0;i<sz;i++)
			for (int j=0;j<=i;j++) update(dp2[i],(ll)dp[j]*D(id[j],id[i],res)%mod);
			dp=dp2;
			lst=z;
		}
		z=x-1;
		if (lst<z) trans(z),lst=z;
		z=x;
		if (lst<z) trans(z),lst=z;
		z=x+1;
		if (lst<z&&z<=c.back()) trans(z),lst=z;
	}
	for (int i=0;i<sz;i++)
		if (L[i]<=c.back()&&c.back()<=R[i]) update(ans,dp[i]);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); ll x; read(x);
	for (int i=1;i<=n;i++) {
		read(x); if (!x) continue;
		if (!a.empty()&&sgn(x)==sgn(a.back())) a.back()+=x;
		else a.push_back(x);
	}
	n=(int)a.size();
	peaks.push_back(1);
	for (int i=0;i<n;i++) peaks.push_back(a[i]+peaks.back());
	n++;
	LIS=1;
	for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
		if (peaks[i]<=peaks[j]) LIS=max(LIS,peaks[j]-peaks[i]+1);
	if (LIS==1) {
		ans=1;
		for (int i=0;i<a.size();i++) update(ans,abs(a[i])%mod);
		printf("1 %d\n",ans);
		return 0;
	}
	int i=0,nxt;
	vector<ll> b;
	while (i<n) {
		nxt=-1;
		for (int j=i+1;j<n;j++) if (peaks[j]-peaks[i]+1==LIS) nxt=j;
		if (nxt==-1) { i++; continue; }
		b.clear();
		for (int j=i;j<=nxt;j++) b.push_back(peaks[j]);
		solve(b);
		i=nxt;
	}
	printf("%lld %d\n",LIS,ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/