#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize ("-ffloat-store")
#include<iostream>
#include<bits/stdc++.h>
#define dbg(args...)

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403() {
#ifdef ARYANC403
	auto end_time = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double> diff = end_time-start_time;
	cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF) {
	return uniform_int_distribution<lli>(l,r)(rng);
}

class CMP {
	public:
		bool operator()(ii a , ii b) {
			return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));
		}
};

void add( map<lli,lli> &m, lli x,lli cnt=1) {
	auto jt=m.find(x);
	if(jt==m.end())         m.insert({x,cnt});
	else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1) {
	auto jt=m.find(x);
	if(jt->Y<=cnt)            m.erase(jt);
	else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b) {
	return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 998244353L;
const lli N = 55;

lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a,b;

lli po(lli a,lli n) {
	if(n==0)
		return 1;
	if(n%2)
		return (a*po(a,n-1))%mod;
	return po(a*a%mod,n/2);
}

vi inv(N+3);

lli solve(vi b,const lli st,const lli ed) {
	b.pb(st);
	sort(all(b));
	b.erase(unique(all(b)),b.end());

	const lli n=sz(b);
	auto gt=[&](const lli v) {
		return upper_bound(all(b),v)-1-b.begin();
	};
	vector<vi> polygons(n,vi(N,0));
	for(lli j=1; j+1<n; ++j)
		polygons[j].resize(min(N,b[j+1]-b[j]+1));
	assert(b[gt(st)]==st);
	assert(b[gt(0)]==0);
	polygons[gt(st)][0]=1;
	if(st==-1)
		polygons[gt(0)][0]=1;

	auto interpolate=[](vi c,lli x) {
		const lli n=sz(c);
		if(0<=x&&x<n)
			return c[x];
		lli p=1;
		for(lli i=0; i<n; ++i) {
			c[i]=(c[i]*p)%mod;
			p=(p*inv[i+1])%mod;
			p=(p*((x-i)%mod))%mod;
		}

		p=1;
		for(lli i=n-1; i>=0; --i) {
			c[i]=(c[i]*p)%mod;
			p=(-p*inv[n-i])%mod;
			p=(p*((x-i)%mod))%mod;
		}

		lli val=0;
		for(auto x:c)
			val+=x;
		val%=mod;
		val+=mod;
		val%=mod;
		dbg("Ht",c,val,x);
		return val;
	};

	auto eval=[&](lli x) {
		const lli pos=gt(x);
		return interpolate(polygons[pos],x-b[pos]);
	};

	lli x=0;
	for(auto gp:a) {
		if(gp==0)
			continue;
		lli l,r;
		ii fac;
		if(gp<0) {
			l=x+gp,r=x-1;
			fac= {0,1};
		} else {
			l=x+1,r=x+gp;
			fac= {1,0};
		}
		dbg(l,r);
		lli nxtol=eval(l-1),nxtne=eval(l-1);
		for(lli i=0; i+1<n; ++i) {
			if(l>=b[i+1]||r<b[i])
				continue;
			dbg("ct",l,r,b[i],b[i+1]-1,nxtne,nxtol);
			lli ol=nxtol,ne=nxtne,tp;
			nxtol=eval(b[i+1]-1);
			auto &cur=polygons[i];
			for(lli j=0; j<sz(cur); ++j) {
				tp=cur[j];
				cur[j]=(cur[j]+fac.X*ne+fac.Y*ol)%mod;
				ne=cur[j];
				ol=tp;
			}
			dbg(cur,b[i+1]-1,eval(b[i+1]-1));
			nxtne=eval(b[i+1]-1);
		}
		dbg("Hello");
		x+=gp;
	}
	return eval(ed);
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	{

		cin>>n>>m;
		lli len=1,l=0,mn=0,cnt=0;
		for(lli i=1; i<N+3; ++i)
			inv[i]=po(i,mod-2);
		b.pb(0);
		b.pb(-1);
		b.pb(1);
		vi cd;
		cd.pb(0);

		fo(i,n) {
			cin>>in;
			a.pb(in);
			cnt+=in;
			b.pb(cnt+1);
			b.pb(cnt);
			b.pb(cnt-1);
			cd.pb(cnt);
			if(len<cnt-mn+1) {
				len=cnt-mn+1;
				l=mn;
			}
			mn=min(mn,cnt);
		}
		dbg(len,l);
		b.pb(-INF);
		b.pb(INF);
		cout<<len<<" ";

		if(len==1) {
			lli ans=1;
			for(auto x:a)
				ans+=-x;
			cout<<ans%mod<<endl;
			return 0;
		}

		sort(all(b));
		b.erase(unique(all(b)),b.end());

		sort(all(cd));
		cd.erase(unique(all(cd)),cd.end());

		lli ans=0;
		for(auto x:cd)
			ans+=solve(b,x-1,x+len-1);
		ans%=mod;
		ans+=mod;
		ans%=mod;

		cout<<ans<<endl;
	}
	aryanc403();
	return 0;
}
### Prompt

Your task is to create a CPP solution to 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
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize ("-ffloat-store")
#include<iostream>
#include<bits/stdc++.h>
#define dbg(args...)

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403() {
#ifdef ARYANC403
	auto end_time = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double> diff = end_time-start_time;
	cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF) {
	return uniform_int_distribution<lli>(l,r)(rng);
}

class CMP {
	public:
		bool operator()(ii a , ii b) {
			return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));
		}
};

void add( map<lli,lli> &m, lli x,lli cnt=1) {
	auto jt=m.find(x);
	if(jt==m.end())         m.insert({x,cnt});
	else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1) {
	auto jt=m.find(x);
	if(jt->Y<=cnt)            m.erase(jt);
	else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b) {
	return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 998244353L;
const lli N = 55;

lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a,b;

lli po(lli a,lli n) {
	if(n==0)
		return 1;
	if(n%2)
		return (a*po(a,n-1))%mod;
	return po(a*a%mod,n/2);
}

vi inv(N+3);

lli solve(vi b,const lli st,const lli ed) {
	b.pb(st);
	sort(all(b));
	b.erase(unique(all(b)),b.end());

	const lli n=sz(b);
	auto gt=[&](const lli v) {
		return upper_bound(all(b),v)-1-b.begin();
	};
	vector<vi> polygons(n,vi(N,0));
	for(lli j=1; j+1<n; ++j)
		polygons[j].resize(min(N,b[j+1]-b[j]+1));
	assert(b[gt(st)]==st);
	assert(b[gt(0)]==0);
	polygons[gt(st)][0]=1;
	if(st==-1)
		polygons[gt(0)][0]=1;

	auto interpolate=[](vi c,lli x) {
		const lli n=sz(c);
		if(0<=x&&x<n)
			return c[x];
		lli p=1;
		for(lli i=0; i<n; ++i) {
			c[i]=(c[i]*p)%mod;
			p=(p*inv[i+1])%mod;
			p=(p*((x-i)%mod))%mod;
		}

		p=1;
		for(lli i=n-1; i>=0; --i) {
			c[i]=(c[i]*p)%mod;
			p=(-p*inv[n-i])%mod;
			p=(p*((x-i)%mod))%mod;
		}

		lli val=0;
		for(auto x:c)
			val+=x;
		val%=mod;
		val+=mod;
		val%=mod;
		dbg("Ht",c,val,x);
		return val;
	};

	auto eval=[&](lli x) {
		const lli pos=gt(x);
		return interpolate(polygons[pos],x-b[pos]);
	};

	lli x=0;
	for(auto gp:a) {
		if(gp==0)
			continue;
		lli l,r;
		ii fac;
		if(gp<0) {
			l=x+gp,r=x-1;
			fac= {0,1};
		} else {
			l=x+1,r=x+gp;
			fac= {1,0};
		}
		dbg(l,r);
		lli nxtol=eval(l-1),nxtne=eval(l-1);
		for(lli i=0; i+1<n; ++i) {
			if(l>=b[i+1]||r<b[i])
				continue;
			dbg("ct",l,r,b[i],b[i+1]-1,nxtne,nxtol);
			lli ol=nxtol,ne=nxtne,tp;
			nxtol=eval(b[i+1]-1);
			auto &cur=polygons[i];
			for(lli j=0; j<sz(cur); ++j) {
				tp=cur[j];
				cur[j]=(cur[j]+fac.X*ne+fac.Y*ol)%mod;
				ne=cur[j];
				ol=tp;
			}
			dbg(cur,b[i+1]-1,eval(b[i+1]-1));
			nxtne=eval(b[i+1]-1);
		}
		dbg("Hello");
		x+=gp;
	}
	return eval(ed);
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	{

		cin>>n>>m;
		lli len=1,l=0,mn=0,cnt=0;
		for(lli i=1; i<N+3; ++i)
			inv[i]=po(i,mod-2);
		b.pb(0);
		b.pb(-1);
		b.pb(1);
		vi cd;
		cd.pb(0);

		fo(i,n) {
			cin>>in;
			a.pb(in);
			cnt+=in;
			b.pb(cnt+1);
			b.pb(cnt);
			b.pb(cnt-1);
			cd.pb(cnt);
			if(len<cnt-mn+1) {
				len=cnt-mn+1;
				l=mn;
			}
			mn=min(mn,cnt);
		}
		dbg(len,l);
		b.pb(-INF);
		b.pb(INF);
		cout<<len<<" ";

		if(len==1) {
			lli ans=1;
			for(auto x:a)
				ans+=-x;
			cout<<ans%mod<<endl;
			return 0;
		}

		sort(all(b));
		b.erase(unique(all(b)),b.end());

		sort(all(cd));
		cd.erase(unique(all(cd)),cd.end());

		lli ans=0;
		for(auto x:cd)
			ans+=solve(b,x-1,x+len-1);
		ans%=mod;
		ans+=mod;
		ans%=mod;

		cout<<ans<<endl;
	}
	aryanc403();
	return 0;
}
```