#include <stdio.h>
#include <sys/time.h>

#define N	50
#define MD	998244353

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec;
	if (X % 2 == 0)
		X++;
}

int rand_() {
	return (X *= 3) >> 1;
}

long long xx[(N + 1) * 2];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void mult(int aa[][N + 1], int bb[][N + 1], int cc[][N + 1], int n) {
	int i, j, k;

	for (i = 0; i < n; i++)
		for (j = i; j < n; j++)
			cc[i][j] = 0;
	for (i = 0; i < n; i++) {
		int *ai = aa[i];

		for (k = i; k < n; k++) {
			int *bk = bb[k], a = ai[k];

			if (a)
				for (j = k; j < n; j++) {
					int b = bk[j];

					if (b)
						cc[i][j] = (cc[i][j] + (long long) a * b) % MD;
				}
		}
	}
}

void power(int aa[][N + 1], int pp[][N + 1], int tt[][N + 1], int n, int k) {
	if (k == 0) {
		int i, j;

		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				pp[i][j] = i == j;
		return;
	}
	if (k % 2 == 0) {
		power(aa, tt, pp, n, k / 2);
		mult(tt, tt, pp, n);
	} else {
		power(aa, pp, tt, n, k / 2);
		mult(pp, pp, tt, n);
		mult(tt, aa, pp, n);
	}
}

int main() {
	static int ii[(N + 1) * 2], aa[N + 1][N + 1], pp[N + 1][N + 1], tt[N + 1][N + 1], aa_[N + 1][N + 1];
	static char up[N + 1], active[N + 1];
	int n, n_, h, h_, h1, i, j, ans2;
	long long ans1, xmin, x, down;

	srand_();
	scanf("%d%lld", &n, &x);
	ans1 = 1, xmin = x = 0, down = 1;
	xx[0 << 1 | 0] = 0, xx[0 << 1 | 1] = 1, n_ = 1;
	for (i = 1; i <= n; i++) {
		int d;

		scanf("%d", &d);
		if (d == 0)
			continue;
		if (d > 0) {
			xx[n_ << 1 | 0] = x + 1, xx[n_ << 1 | 1] = x + d + 1, up[n_] = 1, n_++;
			down = 0;
		} else {
			xx[n_ << 1 | 0] = x + d, xx[n_ << 1 | 1] = x, up[n_] = 0, n_++;
			xmin = min(xmin, x + d);
		}
		x += d;
		ans1 = max(ans1, x - xmin + 1);
	}
	if (down) {
		printf("%lld %lld\n", ans1, (-xmin + 1) % MD);
		return 0;
	}
	n = n_;
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	ans2 = 0;
	for (h = 0; h < n * 2; h = h_) {
		x = xx[ii[h]];
		h_ = h + 1;
		while (h_ < n * 2 && xx[ii[h_]] == x)
			h_++;
		if (h_ == n * 2)
			break;
		for (h1 = h; h1 < h_; h1++) {
			i = ii[h1];
			active[i >> 1] = (i & 1) ^ 1;
		}
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++)
				aa[i][j] = active[j];
			aa[i][i] = active[i] && up[i];
		}
		mult(aa_, aa, tt, n);
		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				aa_[i][j] = tt[i][j];
		for (h1 = h; h1 < h_; h1++) {
			i = ii[h1];
			if ((i & 1) == 0)
				i >>= 1, aa_[i][i] = (aa_[i][i] + 1) % MD;
		}
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++)
				aa[i][j] = active[j];
			aa[i][i] = active[i] && up[i];
		}
		power(aa, pp, tt, n, xx[ii[h_]] - xx[ii[h]] - 1);
		mult(aa_, pp, tt, n);
		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				aa_[i][j] = tt[i][j];
		for (i = 0; i < n; i++)
			if (xx[ii[h_]] - xx[i << 1 | 0] == ans1)
				for (j = i; j < n; j++)
					ans2 = (ans2 + aa_[i][j]) % MD;
	}
	printf("%lld %d\n", ans1, ans2);
	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 <stdio.h>
#include <sys/time.h>

#define N	50
#define MD	998244353

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec;
	if (X % 2 == 0)
		X++;
}

int rand_() {
	return (X *= 3) >> 1;
}

long long xx[(N + 1) * 2];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void mult(int aa[][N + 1], int bb[][N + 1], int cc[][N + 1], int n) {
	int i, j, k;

	for (i = 0; i < n; i++)
		for (j = i; j < n; j++)
			cc[i][j] = 0;
	for (i = 0; i < n; i++) {
		int *ai = aa[i];

		for (k = i; k < n; k++) {
			int *bk = bb[k], a = ai[k];

			if (a)
				for (j = k; j < n; j++) {
					int b = bk[j];

					if (b)
						cc[i][j] = (cc[i][j] + (long long) a * b) % MD;
				}
		}
	}
}

void power(int aa[][N + 1], int pp[][N + 1], int tt[][N + 1], int n, int k) {
	if (k == 0) {
		int i, j;

		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				pp[i][j] = i == j;
		return;
	}
	if (k % 2 == 0) {
		power(aa, tt, pp, n, k / 2);
		mult(tt, tt, pp, n);
	} else {
		power(aa, pp, tt, n, k / 2);
		mult(pp, pp, tt, n);
		mult(tt, aa, pp, n);
	}
}

int main() {
	static int ii[(N + 1) * 2], aa[N + 1][N + 1], pp[N + 1][N + 1], tt[N + 1][N + 1], aa_[N + 1][N + 1];
	static char up[N + 1], active[N + 1];
	int n, n_, h, h_, h1, i, j, ans2;
	long long ans1, xmin, x, down;

	srand_();
	scanf("%d%lld", &n, &x);
	ans1 = 1, xmin = x = 0, down = 1;
	xx[0 << 1 | 0] = 0, xx[0 << 1 | 1] = 1, n_ = 1;
	for (i = 1; i <= n; i++) {
		int d;

		scanf("%d", &d);
		if (d == 0)
			continue;
		if (d > 0) {
			xx[n_ << 1 | 0] = x + 1, xx[n_ << 1 | 1] = x + d + 1, up[n_] = 1, n_++;
			down = 0;
		} else {
			xx[n_ << 1 | 0] = x + d, xx[n_ << 1 | 1] = x, up[n_] = 0, n_++;
			xmin = min(xmin, x + d);
		}
		x += d;
		ans1 = max(ans1, x - xmin + 1);
	}
	if (down) {
		printf("%lld %lld\n", ans1, (-xmin + 1) % MD);
		return 0;
	}
	n = n_;
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	ans2 = 0;
	for (h = 0; h < n * 2; h = h_) {
		x = xx[ii[h]];
		h_ = h + 1;
		while (h_ < n * 2 && xx[ii[h_]] == x)
			h_++;
		if (h_ == n * 2)
			break;
		for (h1 = h; h1 < h_; h1++) {
			i = ii[h1];
			active[i >> 1] = (i & 1) ^ 1;
		}
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++)
				aa[i][j] = active[j];
			aa[i][i] = active[i] && up[i];
		}
		mult(aa_, aa, tt, n);
		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				aa_[i][j] = tt[i][j];
		for (h1 = h; h1 < h_; h1++) {
			i = ii[h1];
			if ((i & 1) == 0)
				i >>= 1, aa_[i][i] = (aa_[i][i] + 1) % MD;
		}
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++)
				aa[i][j] = active[j];
			aa[i][i] = active[i] && up[i];
		}
		power(aa, pp, tt, n, xx[ii[h_]] - xx[ii[h]] - 1);
		mult(aa_, pp, tt, n);
		for (i = 0; i < n; i++)
			for (j = i; j < n; j++)
				aa_[i][j] = tt[i][j];
		for (i = 0; i < n; i++)
			if (xx[ii[h_]] - xx[i << 1 | 0] == ans1)
				for (j = i; j < n; j++)
					ans2 = (ans2 + aa_[i][j]) % MD;
	}
	printf("%lld %d\n", ans1, ans2);
	return 0;
}

```