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>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define abs(x) ((x)>0?(x):-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;

struct type{ll f,g;} ans;
int d[51],A,B,s2,n,N,i,j,k,l,s,sum,X1,X2;
int a[20001][2],pre[20001],t;
type f[20001],F[201];
ll b[201],S[201],js[201][51],x,ss;
ll CC[201][201];

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}

ll C(ll n,ll m)
{
	int i;
	ll s1=1,s2=1;
	
	fo(i,1,m) s1=s1*(n-i+1)%mod,s2=s2*i%mod;
	return s1*qpower(s2,Mod)%mod;
}
void Add(type &a,type b)
{
	if (b.f>=a.f)
	{
		if (b.f>a.f) a=b;
		else add(a.g,b.g);
	}
}

void init()
{
	static int ls[20001];
	sort(b+1,b+t+1);l=1;
	fo(i,2,t) if (b[i]!=b[l]) b[++l]=b[i];t=l;
	fo(i,1,t-1) S[i]=b[i+1]-b[i];
	
	fo(x,1,t) if (!b[x]) break;
	N=1,a[N][0]=x,a[N][1]=0;
	fo(i,1,n)
	{
		s=abs(d[i]);
		if (d[i]>0) {while (s) ++x,++N,a[N][0]=x,a[N][1]=0,s-=S[x];}
		else {while (s) --x,s-=S[x],++N,a[N][0]=x,a[N][1]=1;}
	}
	fo(i,1,N) pre[i]=ls[a[i][0]],ls[a[i][0]]=i;
	
	fo(i,1,t-1)
	if (S[i]>1)
	{
		fo(A,1,n)
		{
			B=A-1;s2=S[i]-2;
			fo(k,0,min(B,s2)) add(js[i][A],CC[B][k]*C((s2-k)+A-1,A-1));
		}
	}
}

int main()
{
//	freopen("CF1474F.in","r",stdin);
//	#ifdef file
//	freopen("CF1474F.out","w",stdout);
//	#endif
	
	CC[0][0]=1;
	fo(i,1,200)
	{
		CC[i][0]=CC[i][i]=1;
		fo(j,1,i-1) CC[i][j]=(CC[i-1][j-1]+CC[i-1][j])%mod;
	}
	scanf("%d",&n);
	scanf("%d",&l);x=0;t=2,b[1]=0,b[2]=1;
	fo(i,1,n) scanf("%d",&d[i]),x+=d[i],b[++t]=x,b[++t]=x+1;
	init();
	
	f[N+1]=type{0,1};
	fo(i,1,t) F[i]=type{0,1};
	fd(i,N,1)
	{
		X1=a[i][0],X2=a[i][1];
		if (!X2) Add(f[i],type{F[X1+1].f+S[X1],F[X1+1].g});
		else Add(f[i],type{F[X1+1].f+1,F[X1+1].g*S[X1]%mod});
		
		if (S[X1]>1)
		{
			sum=1;
			for (j=pre[i]; j; j=pre[j])
			{
				++sum;
				A=B=sum/2;
				if (sum&1) {if (!X2) ++A; else ++B;}
				s2=S[X1]-2;B=A-1;
				
				Add(f[j],type{F[X1+1].f+S[X1],F[X1+1].g*js[X1][A]%mod});
			}
		}
		Add(F[X1],f[i]);
	}
	fo(i,1,N) Add(ans,f[i]);
	
	printf("%lld %lld\n",ans.f,(ans.g+mod)%mod);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}