#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long int
#define mod 998244353
inline int sum(int a,int b){return a+b<mod?a+b:a+b-mod;}
inline int mul(int a,int b){return (int)((ll)a*b%mod);}
inline int pow(int a,int b)
{
	int res=1;
	while(b>0){
		if(b&1) res=mul(res,a);
		a=mul(a,a); b>>=1;
	}
	return res;
}
inline int inv(int x){return pow(x,mod-2);}

int n,m=0,t,ans=0;
ll l[50],r[50],pos[150];
struct matrix{
	int m[50][50];
	matrix(void){
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++)
				m[i][j]=m[j][i]=0;
			m[i][i]=1;
		}
		return;
	}
};
matrix mmul(matrix m1,matrix m2)
{
	matrix M;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			M.m[i][j]=0;
			for(int k=0;k<n;k++)
				M.m[i][j]=sum(M.m[i][j],mul(m1.m[i][k],m2.m[k][j]));
		}
	return M;
}
matrix mpow(matrix m,ll k)
{
	matrix M;
	while(k>0){
		if(k&1) M=mmul(M,m);
		m=mmul(m,m); k>>=1;
	}
	return M;
}

namespace solver
{
	int n,m;
	ll p[50],q[50];
	void prepare(int L,int R)
	{
		n=R-L+1; m=0;
		for(int i=0;i<n;i++){
			p[i]=l[i+L];
			q[i]=r[i+L];
		}
		bool opt=0;
		for(int i=0;i<n;i++){
			if(p[i]==q[i]){
				p[i]=q[i]=1e18;
				continue;
			}
			if(opt&&p[i]<=q[i]){
				p[i]++;
				if(i<n-1) q[i]--;
				if(p[i]>q[i]) p[i]=q[i]=1e18;
			}
			else if(opt&&p[i]>q[i]){
				p[i]--; q[i]++;
				if(p[i]<q[i]) p[i]=q[i]=1e18;
			}
			if(p[i]<1e18){
				pos[m++]=p[i]; pos[m++]=q[i];
			}
			opt^=1;
		}
		sort(pos,pos+m);
		return;
	}
	
	inline bool check(int a,ll k)
	{
		return (p[a]<=k&&k<=q[a])||(p[a]>=k&&k>=q[a]);
	}
	int res[50],temp[50];
	inline void update(ll& nowk)
	{
		for(int x=0;x<n;x++){
			temp[x]=0;
			for(int y=0;y<x;y++)
				if(check(y,nowk))
					temp[x]=sum(temp[x],res[y]);
			if(p[x]<=nowk&&nowk<=q[x])
				temp[x]=sum(temp[x],res[x]);
		}
		nowk++;
		for(int x=0;x<n;x++)
			if(!check(x,nowk))
				temp[x]=0;
		for(int x=0;x<n;x++)
			res[x]=temp[x];
		return;
	}
	
	int solve(int L,int R)
	{
		prepare(L,R);
		ll nowk=pos[0];
		for(int i=0;i<n;i++)
			if(check(i,nowk))
				res[i]=1;
			else res[i]=0;
		for(int i=0;i<m;i++){
			if(nowk<pos[i])
				update(nowk);
			if(i<m-1){
				if(nowk==pos[i]&&nowk<pos[m-1])
					update(nowk);
				matrix m1;
				for(int x=0;x<n;x++){
					for(int y=x+1;y<n;y++)
						if(check(x,nowk)&&check(y,nowk))
							m1.m[x][y]=1;
					if(p[x]>nowk||nowk>q[x])
						m1.m[x][x]=0;
				}
				ll k=pos[i+1]-1-nowk;
				matrix m2=mpow(m1,k);
				for(int x=0;x<n;x++){
					temp[x]=0;
					for(int y=0;y<n;y++)
						temp[x]=sum(temp[x],mul(res[y],m2.m[y][x]));
				}
				for(int x=0;x<n;x++)
					res[x]=temp[x];
				nowk=max(nowk,pos[i+1]-1);
			}
		}
		int ans=0;
		for(int i=0;i<n;i++)
			if(p[i]==pos[m-1]||q[i]==pos[m-1])
				ans=sum(ans,res[i]);
		return ans;
	}
}

bool checkup(void)
{
	for(int i=0;i<n;i++)
		if(l[i]<r[i])
			return 0;
	return 1;
}
int main(void)
{
	scanf("%d%lld",&n,&l[0]);
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		r[i]=l[i]+t;
		if(i!=n-1) l[i+1]=r[i];
	}
	if(checkup()){
		printf("1 %lld\n",(l[0]-r[n-1]+1)%mod);
		return 0;
	}
	int d=0,ans2=0;
	ll ans1=0;
	while(d<n){
		int mx=d,mn=d;
		for(int i=d;i<n;i++)
			if(r[mx]<=r[i])
				mx=i;
		for(int i=d;i<=mx;i++)
			if(l[mn]>l[i])
				mn=i;
		if(ans1<r[mx]-l[mn]+1)
			ans2=0;
		if(ans1<=r[mx]-l[mn]+1){
			ans1=r[mx]-l[mn]+1;
			ans2=sum(ans2,solver::solve(mn,mx));
		}
		d=mx+1;
	}
	printf("%lld %d\n",ans1,ans2);
	return 0;
}
/*
9 0
4 -4 4 -4 4 -4 4 -1000000 1000
*/
### Prompt

In Cpp, your task is to solve the following 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].

### Response

```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long int
#define mod 998244353
inline int sum(int a,int b){return a+b<mod?a+b:a+b-mod;}
inline int mul(int a,int b){return (int)((ll)a*b%mod);}
inline int pow(int a,int b)
{
	int res=1;
	while(b>0){
		if(b&1) res=mul(res,a);
		a=mul(a,a); b>>=1;
	}
	return res;
}
inline int inv(int x){return pow(x,mod-2);}

int n,m=0,t,ans=0;
ll l[50],r[50],pos[150];
struct matrix{
	int m[50][50];
	matrix(void){
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++)
				m[i][j]=m[j][i]=0;
			m[i][i]=1;
		}
		return;
	}
};
matrix mmul(matrix m1,matrix m2)
{
	matrix M;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			M.m[i][j]=0;
			for(int k=0;k<n;k++)
				M.m[i][j]=sum(M.m[i][j],mul(m1.m[i][k],m2.m[k][j]));
		}
	return M;
}
matrix mpow(matrix m,ll k)
{
	matrix M;
	while(k>0){
		if(k&1) M=mmul(M,m);
		m=mmul(m,m); k>>=1;
	}
	return M;
}

namespace solver
{
	int n,m;
	ll p[50],q[50];
	void prepare(int L,int R)
	{
		n=R-L+1; m=0;
		for(int i=0;i<n;i++){
			p[i]=l[i+L];
			q[i]=r[i+L];
		}
		bool opt=0;
		for(int i=0;i<n;i++){
			if(p[i]==q[i]){
				p[i]=q[i]=1e18;
				continue;
			}
			if(opt&&p[i]<=q[i]){
				p[i]++;
				if(i<n-1) q[i]--;
				if(p[i]>q[i]) p[i]=q[i]=1e18;
			}
			else if(opt&&p[i]>q[i]){
				p[i]--; q[i]++;
				if(p[i]<q[i]) p[i]=q[i]=1e18;
			}
			if(p[i]<1e18){
				pos[m++]=p[i]; pos[m++]=q[i];
			}
			opt^=1;
		}
		sort(pos,pos+m);
		return;
	}
	
	inline bool check(int a,ll k)
	{
		return (p[a]<=k&&k<=q[a])||(p[a]>=k&&k>=q[a]);
	}
	int res[50],temp[50];
	inline void update(ll& nowk)
	{
		for(int x=0;x<n;x++){
			temp[x]=0;
			for(int y=0;y<x;y++)
				if(check(y,nowk))
					temp[x]=sum(temp[x],res[y]);
			if(p[x]<=nowk&&nowk<=q[x])
				temp[x]=sum(temp[x],res[x]);
		}
		nowk++;
		for(int x=0;x<n;x++)
			if(!check(x,nowk))
				temp[x]=0;
		for(int x=0;x<n;x++)
			res[x]=temp[x];
		return;
	}
	
	int solve(int L,int R)
	{
		prepare(L,R);
		ll nowk=pos[0];
		for(int i=0;i<n;i++)
			if(check(i,nowk))
				res[i]=1;
			else res[i]=0;
		for(int i=0;i<m;i++){
			if(nowk<pos[i])
				update(nowk);
			if(i<m-1){
				if(nowk==pos[i]&&nowk<pos[m-1])
					update(nowk);
				matrix m1;
				for(int x=0;x<n;x++){
					for(int y=x+1;y<n;y++)
						if(check(x,nowk)&&check(y,nowk))
							m1.m[x][y]=1;
					if(p[x]>nowk||nowk>q[x])
						m1.m[x][x]=0;
				}
				ll k=pos[i+1]-1-nowk;
				matrix m2=mpow(m1,k);
				for(int x=0;x<n;x++){
					temp[x]=0;
					for(int y=0;y<n;y++)
						temp[x]=sum(temp[x],mul(res[y],m2.m[y][x]));
				}
				for(int x=0;x<n;x++)
					res[x]=temp[x];
				nowk=max(nowk,pos[i+1]-1);
			}
		}
		int ans=0;
		for(int i=0;i<n;i++)
			if(p[i]==pos[m-1]||q[i]==pos[m-1])
				ans=sum(ans,res[i]);
		return ans;
	}
}

bool checkup(void)
{
	for(int i=0;i<n;i++)
		if(l[i]<r[i])
			return 0;
	return 1;
}
int main(void)
{
	scanf("%d%lld",&n,&l[0]);
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		r[i]=l[i]+t;
		if(i!=n-1) l[i+1]=r[i];
	}
	if(checkup()){
		printf("1 %lld\n",(l[0]-r[n-1]+1)%mod);
		return 0;
	}
	int d=0,ans2=0;
	ll ans1=0;
	while(d<n){
		int mx=d,mn=d;
		for(int i=d;i<n;i++)
			if(r[mx]<=r[i])
				mx=i;
		for(int i=d;i<=mx;i++)
			if(l[mn]>l[i])
				mn=i;
		if(ans1<r[mx]-l[mn]+1)
			ans2=0;
		if(ans1<=r[mx]-l[mn]+1){
			ans1=r[mx]-l[mn]+1;
			ans2=sum(ans2,solver::solve(mn,mx));
		}
		d=mx+1;
	}
	printf("%lld %d\n",ans1,ans2);
	return 0;
}
/*
9 0
4 -4 4 -4 4 -4 4 -1000000 1000
*/
```