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 <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#define int long long

namespace Poly
{
	const int K = 60, mod = 998244353; typedef long long ll;

	int qpow(int x, int k)
	{
		int rs = 1; while (k) { if (k & 1) rs = (ll)rs * x % mod; x = (ll)x * x % mod, k >>= 1; } return rs;
	}

	struct Poly { int f[K + 5]; };

	int a[K + 5][K + 5], as[K + 5];
	
	Poly Make(int b) { Poly* x = new Poly; memset((*x).f, 0, sizeof (*x).f); (*x).f[0] = b; return *x; }

	Poly Lagrange(std::vector<int> x, std::vector<int> y)
	{
		for (int i = 0; i <= K; i++) a[i][0] = 1;
		for (int i = 0; i <= K; i++) for (int j = 1; j <= K; j++) a[i][j] = (ll)a[i][j - 1] * x[i] % mod;
		for (int i = 0; i <= K; i++) a[i][K + 1] = y[i];
		for (int j = 0; j <= K; j++)
		{
			for (int i = j; i <= K; i++) if (a[i][j]) { std::swap(a[i], a[j]); break; }
			int t = qpow(a[j][j], mod - 2);
			for (int k = j; k <= K + 1; k++) a[j][k] = (ll)a[j][k] * t % mod;
			for (int i = j + 1; i <= K; i++)
			{
				int tt = mod - a[i][j];
				for (int k = j; k <= K + 1; k++) a[i][k] = ((ll)a[i][k] + (ll)tt * a[j][k]) % mod;
			}
		}
		for (int i = K; i >= 0; i--)
		{
			as[i] = a[i][K + 1];
			for (int k = i - 1; k >= 0; k--) a[k][K + 1] = ((ll)a[k][K + 1] + (ll)(mod - as[i]) * a[k][i]) % mod;
		}
		Poly rs = Make(0); for (int i = 0; i <= K; i++) rs.f[i] = as[i]; return rs;
	}

	int Calculate(const Poly& A, int x)
	{
		x = x % mod; as[0] = 1; for (int i = 1; i <= K; i++) as[i] = (ll)as[i - 1] * x % mod;
		int rs = 0;
		for (int i = 0; i <= K; i++) rs = (rs + (ll)A.f[i] * as[i]) % mod; return rs;
	}
}

const int maxn = 5005;

int n, d[maxn]; Poly::ll ps[maxn], mn, hs, NM;

struct node { Poly::ll l, r; Poly::Poly dp; }; node dp[100005]; int tt, tp[100005];

int calc(int x)
{
	for (int i = 1; i <= tt; i++) if (dp[i].l <= x && x <= dp[i].r) return Poly::Calculate(dp[i].dp, x);
	return 1;
}

#define cerr std::cerr
#define endl std::endl

void Make(int ps) { dp[tt = 1] = { mn = hs = ps, ps, Poly::Make(1) }; }

void Insert(int hh) { dp[++tt] = { hs + 1, hh, Poly::Make(calc(hs)) }, hs = hh; }

void preMod() { /*cerr << "preMod: " << tt << endl;*/ for (int i = 1; i <= tt; i++) tp[i] = calc(dp[i].l - 1); }

void Modify0(int i, int ty)
{//cerr << "Mod0" << i << ' ' << tt << endl;
	if (dp[i].l == dp[i].r) { dp[i].dp.f[0] = (dp[i].dp.f[0] + (ty ? calc(dp[i].l - 1) : tp[i])) % Poly::mod; return; }
	int vl[Poly::K + 5];
	for (int j = dp[i].l; j <= dp[i].l + Poly::K; j++) vl[j - dp[i].l] = Poly::Calculate(dp[i].dp, j);
	for (int j = Poly::K; j; j--) vl[j] = (vl[j] + vl[j - 1]) % Poly::mod;
	dp[++tt] = { dp[i].l, dp[i].l, Poly::Make(vl[0] = (vl[0] + (ty ? calc(dp[i].l - 1) : tp[i])) % Poly::mod) };
	std::vector<int> x, y;
	for (int j = dp[i].l + 1; j <= dp[i].l + Poly::K; j++) x.push_back(j);
	for (int j = dp[i].l + 1; j <= dp[i].l + Poly::K; j++) y.push_back(vl[j - dp[i].l]);
	x.push_back(dp[i].l + Poly::K + 1);
	y.push_back(Poly::Calculate(dp[i].dp, dp[i].l + Poly::K) + Poly::Calculate(dp[i].dp, dp[i].l + Poly::K + 1));
	dp[i].dp = Poly::Lagrange(x, y), dp[i].l++;
}

void Modify1(int l, int r)
{
	if (l > r) return;
	int nt = tt;
	for (int i = 1; i <= nt; i++) if (l <= dp[i].r && r >= dp[i].l)
	{//cerr << "Mod1" << i << ' ' << tt << ' ' << dp[i].l << ' ' << dp[i].r << endl;
		if (l <= dp[i].l && dp[i].r <= r) Modify0(i, 0);
		else if (dp[i].l < l && r < dp[i].r)
		{
			dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].l = l, dp[i].r = r;
			Modify0(i, 1);
		}
		else if (dp[i].l == l) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].r = r, Modify0(i, 0);
		else if (dp[i].r == r) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[i].l = l, Modify0(i, 1);
		else if (r > dp[i].r) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[i].l = l, Modify0(i, 1);
		else if (l < dp[i].l) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].r = r, Modify0(i, 0);
		else { exit(0 * puts("!!!!")); }
		//else if (dp[i].l <= l && l <= dp[i].r) { if (l != dp[i].l) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }; dp[i].l = l, Modify0(i, 1); }
		//else { if (dp[i].r != r) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }; dp[i].r = r, Modify0(i, 0); }
	}
}

void Modify2(int i)
{//cerr << "Mod2" << i << ' ' << tt << endl;
	if (dp[i].l == dp[i].r) { dp[i].dp.f[0] = (dp[i].dp.f[0] + calc(dp[i].l - 1)) % Poly::mod; return; }
	int vl[Poly::K + 5];
	for (int j = dp[i].l; j <= dp[i].l + Poly::K; j++) vl[j - dp[i].l] = Poly::Calculate(dp[i].dp, j);
	dp[++tt] = { dp[i].l, dp[i].l, Poly::Make(vl[0] = (vl[0] + calc(dp[i].l - 1)) % Poly::mod) };
	for (int j = 1; j <= Poly::K; j++) vl[j] = (vl[j] + vl[j - 1]) % Poly::mod;
	std::vector<int> x, y;
	for (int j = dp[i].l + 1; j <= dp[i].l + Poly::K; j++) x.push_back(j);
	for (int j = dp[i].l + 1; j <= dp[i].l + Poly::K; j++) y.push_back(vl[j - dp[i].l]);
	x.push_back(dp[i].l + Poly::K + 1);
	y.push_back(vl[Poly::K] + Poly::Calculate(dp[i].dp, dp[i].l + Poly::K + 1));
	dp[i].dp = Poly::Lagrange(x, y), dp[i].l++;
}

void Modify3(int l, int r)
{
	if (l > r) return;
	int nt = tt;
	for (int i = 1; i <= nt; i++) if (l <= dp[i].r && r >= dp[i].l)
	{//cerr << "Mod3" << i << ' ' << tt << ' ' << dp[i].l << ' ' << dp[i].r << endl;
		if (l <= dp[i].l && dp[i].r <= r) Modify2(i);
		else if (dp[i].l < l && r < dp[i].r)
		{
			dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].l = l, dp[i].r = r;
			Modify2(i);
		}
		else if (dp[i].l == l) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].r = r, Modify2(i);
		else if (dp[i].r == r) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[i].l = l, Modify2(i);
		else if (r > dp[i].r) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }, dp[i].l = l, Modify2(i);
		else if (l < dp[i].l) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }, dp[i].r = r, Modify2(i);
		else { exit(0 * puts("!!!!")); }
		//else if (dp[i].l <= l && l <= dp[i].r) { if (l != dp[i].l) dp[++tt] = { dp[i].l, l - 1, dp[i].dp }; dp[i].l = l, Modify2(i); }
		//else { if (r != dp[i].r) dp[++tt] = { r + 1, dp[i].r, dp[i].dp }; dp[i].r = r, Modify2(i); }
	}
}

Poly::ll a0[maxn], as[maxn]; int ttt = 0;

signed main()
{
	/*std::vector<int> x, y;
	for (int i = 0; i <= Poly::K; i++) x.push_back(0), y.push_back(0);
	x[0] = y[0] = 1, x[1] = 2, y[1] = 4;
	Poly::Poly p = Poly::Lagrange(x, y);
	return 0;*/
	scanf("%lld%lld", &n, &ps[0]);
	//if (n == 5 && ps[0] == 34) return 0 * puts("1393 3876");
	for (int i = 1; i <= n; i++) scanf("%lld", d + i);
	for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + d[i];
	//if (n == 50 && ps[1] == 1000001234) return 0 * puts("1024000001 562344234");
	//if (n == 50 && ps[1] == -1000000000) return 0 * puts("1048077054 672819925");
	bool flg = 1;
	for (int i = 1; i <= n; i++) if (d[i] > 0) flg = 0;
	if (flg)
	{
		printf("1 %lld\n", (ps[0] - ps[n] + 1) % Poly::mod);
		return 0; 
	}
	Make(ps[0]), ttt++;
	for (int i = 1; i <= n; i++)
	{
//		cerr << "!!!" << i << ' ' << ttt << endl;
		if (d[i] == 0) continue;
		std::sort(dp + 1, dp + tt + 1, [](node x, node y) { return x.l < y.l; });
		preMod();
		if (ps[i] < mn) Make(ps[i]), ttt++/*, cerr << "MAKE: " << i << ' ' << ttt << endl*/;
		else if (ps[i] > hs) Modify3(ps[i - 1] + 1, hs), Insert(ps[i]);
		else if (d[i] < 0) Modify1(ps[i], ps[i - 1] - 1);
		else Modify3(ps[i - 1] + 1, ps[i]);
//		cerr << "END: " << i << ' ' << ttt << endl;
//		if (ttt > 1000000) ttt = 2;
		if (ps[i] - mn >= a0[ttt]) a0[ttt] = ps[i] - mn, as[ttt] = calc(hs);
	}
	Poly::ll mx = 0, As = 0;
	for (int i = 1; i <= ttt; i++) mx = std::max(mx, a0[i]);
	for (int i = 1; i <= ttt; i++) if (a0[i] == mx) As = (As + as[i]) % Poly::mod;
	printf("%lld %lld\n", mx + 1, (As + Poly::mod) % Poly::mod); return 0;
}