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 signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------


int N,X;
ll S[55];
const ll mo=998244353;

const int MAT=55;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	int pre=0;
	FOR(i,N) {
		cin>>x;
		if(x==0) {
			i--,N--;
			continue;
		}
		if(pre==0) {
			S[i+1]=S[i]+x;
			pre=x;
		}
		else if((x>0)==(pre>0)) {
			S[i]+=x;
			i--,N--;
		}
		else {
			S[i+1]=S[i]+x;
			pre=x;
		}
	}
	S[N+1]=S[N];
	
	
	ll ma=0,mi=0,d=0;
	vector<ll> V;
	FOR(i,N+1) {
		V.push_back(S[i]);
		V.push_back(S[i]-1);
		V.push_back(S[i]+1);
		ma=max(ma,S[i]);
		mi=min(mi,S[i]);
		d=max(d,S[i]-mi);
	}
	
	if(d==0) {
		cout<<1<<" "<<(-S[N]+1)%mo<<endl;
		return;
	}
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	
	Mat A;
	FOR(y,N+1) FOR(x,y) if(S[y]-S[x]==d) A.v[x][x]=1;
	FOR(i,V.size()-1) {
		ll a=V[i];
		ll b=V[i+1];
		
		{
			Mat B;
			mi=0;
			FOR(j,N+1) {
				mi=min(mi,S[j]);
				if(mi==S[j]&&b<=mi) B.v[j][j]=1;
				if(S[j]<S[j+1]&&S[j]<=a&&b<S[j+1]) B.v[j][j]=1;
				if((S[j]<=a&&a<=S[j+1])||(S[j]>=a&&S[j+1]<=a)) {
					for(k=j+1;k<N;k++) {
						if((S[k]<=b&&b<S[k+1])||(S[k]>=b&&S[k+1]<b)) {
							B.v[k][j]=1;
						}
					}
					if(b==S[N]) B.v[N][j]=1;
				}
			}
			ma=-1LL<<60;
			for(j=N;j>=0;j--) {
				ma=max(ma,S[j]);
				if(S[j]==ma&&a>=S[j]) B.v[j][j]=1;
			}
			B=powmat(b-a,B,N+1);
			A=mulmat(B,A,N+1);
		}
	}
	ll ret=0;
	FOR(y,N+1) FOR(x,y) if(S[y]-S[x]==d) ret+=A.v[y][x];
	cout<<(d+1)<<" "<<ret%mo<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}