#include <bits/stdc++.h>
#include"map"
#include"string"
#include"cmath"
#include"cstdio"
#include"iostream"
#include"cstring"
#include"algorithm"
#include"vector"
//#pragma GCC optimize(3, "Ofast")
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define f(i, l, r) for (int i = l; i <= r; ++i)
#define rf(i, r, l) for (int i = r; i >= l; --i)
#define all(x) (x).begin(), (x).end()
#define l l
#define r r
#define lch (o << 1)
#define rch (o << 1 | 1)
#define mid ((l + r) >> 1)
#define mem(x, y) memset(x, y, sizeof(x))
#define mod1(x) ((x >= mod) && (x -= mod))
#define mod2(x) ((x < 0) && (x += mod))

const int inf = 2e9 + 7;
//const ll INF = INT64_MAX;
double eps = 1e-6;
const int mod = 998244353;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
ll power(ll a, ll b) { ll res = 1; while (b) { if (b & 1)res = res * a % mod; a = a * a % mod; b >>= 1; }return res; }
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll exgcd(ll a, ll b, ll& x, ll& y) { ll c; return !b ? (x = 1, y = 0, a) : (c = exgcd(b, a % b, y, x), y -= (a / b) * x, c); }
ll INV(ll a) { ll x, y; exgcd(a, mod, x, y); x %= mod; if (x < 0)x += mod; return x; }
/*int len, C[N], clen;
int id(int v) { return lower_bound(C + 1, C + len, v) - C; }
void initC() { sort(C + 1, C + clen+1); len = unique(C + 1, C + 1 + clen) - C - 1; }*/

void add(int& a, int b) {
	a += b; mod1(a); mod2(a);
}
const int M = 50;
int LL, RR;
struct matrix
{
	int a[M + 1][M + 1];
	matrix() { mem(a, 0); }
	matrix operator*(const matrix& b)const {
		matrix res;
		f(i, LL, RR)f(j, LL, RR)f(k, LL, j)
			res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * b.a[k][j]) % mod;
		return res;
	}
	void init() { mem(a, 0); }
}mat;
matrix power(matrix a, ll b) {
	matrix res;
	f(i, 1, M)res.a[i][i] = 1;
	while (b) {
		if (b & 1)res = res * a;
		a = a * a;
		b >>= 1;
	}return res;
}
vector<int> operator*(const vector<int>& a, const matrix& b) {
	int n = a.size();
	vector<int> res(a.size());
	f(i, 1, n - 1) {
		ll tmp = 0;
		f(j, 1, i)tmp += (ll)a[j] * b.a[j][i] % mod;
		res[i] = tmp % mod;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef local
	freopen("in.txt", "r", stdin);
	int start = clock();
#endif
	int n, x; cin >> n >> x;
	vector<ll> D(n);
	for (auto& i : D)cin >> i;
	vector<ll> d(1);
	for (auto i : D)
		if (i == 0)continue;
		else if (d.back() == 0)d.back() += i;
		else if ((double)i * d.back() > 0)d.back() += i;
		else d.push_back(i);
	n = d.size();
	if (n == 1) {
		if (d.back() <= 0) {
			cout << 1 << " " << (abs(d.back()) + 1)%mod;
		}
		else if (d.back() > 0) {
			cout << d.back() + 1 << " " << 1;
		}
		return 0;
	}
	vector<pair<ll, ll>> seg(1);
	ll now = 0;
	for (auto DD : d) {
		if (DD > 0) {
			seg.push_back({ now + 1,now + DD });
			now += DD;
		}
		else if (DD < 0) {
			seg.push_back({ now - 1,now + DD });
			now += DD;
		}
	}
	seg[1].first = 0;
	set<ll> st;
	f(i, 1, n) {
		st.insert(min(seg[i].first, seg[i].second)); st.insert(max(seg[i].first, seg[i].second) + 1);
	}
	vector<ll> vt; for (auto it : st)vt.push_back(it);

	ll len = 0;
	vector<ll> pre(n + 1);
	pre[0] = 0;
	f(i, 1, n) {
		pre[i] = min(pre[i - 1], min(seg[i].first, seg[i].second));
		if (seg[i].first <= seg[i].second)
			len = max(len, max(seg[i].first, seg[i].second) - pre[i - 1] + 1);
	}
	vector<ll> beginval;
	f(i, 1, n) {
		if (seg[i].first <= seg[i].second)
			if (max(seg[i].first, seg[i].second) - pre[i - 1] + 1 == len)
				beginval.push_back(pre[i - 1]);
	}
	sort(all(beginval));
	beginval.erase(unique(all(beginval)), beginval.end());
	ll res = 0;
	debug(beginval);
	debug(seg);
	debug(vt);
	for (auto down : beginval) {
		f(i, 1, n)if (min(seg[i].first, seg[i].second) == down) {
			LL = i; break;
		}
		rf(i, n, 1)if (max(seg[i].first, seg[i].second) == down + len - 1) {
			RR = i; break;
		}
		vector<int> w(n + 1);
		f(i, 1, n)if (min(seg[i].first, seg[i].second) == down)w[i] = 1;
		debug(down, w);
		int m = vt.size();
		f(i, 0, m - 2) {
			ll L = vt[i], R = vt[i + 1] - 1;
			if (L < down)continue;
			vector<bool> ok(n + 1);
			f(i, 1, n)if (min(seg[i].first, seg[i].second) <= L && R <= max(seg[i].first, seg[i].second))ok[i] = 1;
			if (L != R) {
				mat.init();
				f(i, 1, n)f(j, i, n)if (ok[i] && ok[j])mat.a[i][j] = 1;
				f(i, 1, n)if (seg[i].first > seg[i].second)mat.a[i][i] = 0;
				mat = power(mat, R - L);
				w = w * mat;
				debug(L, R, w);
			}
			if (R == down + len - 1)break;
			mat.init();
			f(i, 1, n)f(j, i, n)
				if (ok[i])
					if (min(seg[j].first, seg[j].second) <= R + 1 && R + 1 <= max(seg[j].first, seg[j].second))
						mat.a[i][j] = 1;
			f(i, 1, n)if (seg[i].first > seg[i].second)mat.a[i][i] = 0;
			w = w * mat;
			debug(R + 1, w);
		}
		f(i, 1, n)if (max(seg[i].first, seg[i].second) == down + len - 1)res += w[i] % mod;
	}
	cout << len << " " << res % mod;
#ifdef local
	int end = clock();
	//cout << '\n' << end - start << "ms";
#endif* /
}
### 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 <bits/stdc++.h>
#include"map"
#include"string"
#include"cmath"
#include"cstdio"
#include"iostream"
#include"cstring"
#include"algorithm"
#include"vector"
//#pragma GCC optimize(3, "Ofast")
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define f(i, l, r) for (int i = l; i <= r; ++i)
#define rf(i, r, l) for (int i = r; i >= l; --i)
#define all(x) (x).begin(), (x).end()
#define l l
#define r r
#define lch (o << 1)
#define rch (o << 1 | 1)
#define mid ((l + r) >> 1)
#define mem(x, y) memset(x, y, sizeof(x))
#define mod1(x) ((x >= mod) && (x -= mod))
#define mod2(x) ((x < 0) && (x += mod))

const int inf = 2e9 + 7;
//const ll INF = INT64_MAX;
double eps = 1e-6;
const int mod = 998244353;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
ll power(ll a, ll b) { ll res = 1; while (b) { if (b & 1)res = res * a % mod; a = a * a % mod; b >>= 1; }return res; }
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll exgcd(ll a, ll b, ll& x, ll& y) { ll c; return !b ? (x = 1, y = 0, a) : (c = exgcd(b, a % b, y, x), y -= (a / b) * x, c); }
ll INV(ll a) { ll x, y; exgcd(a, mod, x, y); x %= mod; if (x < 0)x += mod; return x; }
/*int len, C[N], clen;
int id(int v) { return lower_bound(C + 1, C + len, v) - C; }
void initC() { sort(C + 1, C + clen+1); len = unique(C + 1, C + 1 + clen) - C - 1; }*/

void add(int& a, int b) {
	a += b; mod1(a); mod2(a);
}
const int M = 50;
int LL, RR;
struct matrix
{
	int a[M + 1][M + 1];
	matrix() { mem(a, 0); }
	matrix operator*(const matrix& b)const {
		matrix res;
		f(i, LL, RR)f(j, LL, RR)f(k, LL, j)
			res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * b.a[k][j]) % mod;
		return res;
	}
	void init() { mem(a, 0); }
}mat;
matrix power(matrix a, ll b) {
	matrix res;
	f(i, 1, M)res.a[i][i] = 1;
	while (b) {
		if (b & 1)res = res * a;
		a = a * a;
		b >>= 1;
	}return res;
}
vector<int> operator*(const vector<int>& a, const matrix& b) {
	int n = a.size();
	vector<int> res(a.size());
	f(i, 1, n - 1) {
		ll tmp = 0;
		f(j, 1, i)tmp += (ll)a[j] * b.a[j][i] % mod;
		res[i] = tmp % mod;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef local
	freopen("in.txt", "r", stdin);
	int start = clock();
#endif
	int n, x; cin >> n >> x;
	vector<ll> D(n);
	for (auto& i : D)cin >> i;
	vector<ll> d(1);
	for (auto i : D)
		if (i == 0)continue;
		else if (d.back() == 0)d.back() += i;
		else if ((double)i * d.back() > 0)d.back() += i;
		else d.push_back(i);
	n = d.size();
	if (n == 1) {
		if (d.back() <= 0) {
			cout << 1 << " " << (abs(d.back()) + 1)%mod;
		}
		else if (d.back() > 0) {
			cout << d.back() + 1 << " " << 1;
		}
		return 0;
	}
	vector<pair<ll, ll>> seg(1);
	ll now = 0;
	for (auto DD : d) {
		if (DD > 0) {
			seg.push_back({ now + 1,now + DD });
			now += DD;
		}
		else if (DD < 0) {
			seg.push_back({ now - 1,now + DD });
			now += DD;
		}
	}
	seg[1].first = 0;
	set<ll> st;
	f(i, 1, n) {
		st.insert(min(seg[i].first, seg[i].second)); st.insert(max(seg[i].first, seg[i].second) + 1);
	}
	vector<ll> vt; for (auto it : st)vt.push_back(it);

	ll len = 0;
	vector<ll> pre(n + 1);
	pre[0] = 0;
	f(i, 1, n) {
		pre[i] = min(pre[i - 1], min(seg[i].first, seg[i].second));
		if (seg[i].first <= seg[i].second)
			len = max(len, max(seg[i].first, seg[i].second) - pre[i - 1] + 1);
	}
	vector<ll> beginval;
	f(i, 1, n) {
		if (seg[i].first <= seg[i].second)
			if (max(seg[i].first, seg[i].second) - pre[i - 1] + 1 == len)
				beginval.push_back(pre[i - 1]);
	}
	sort(all(beginval));
	beginval.erase(unique(all(beginval)), beginval.end());
	ll res = 0;
	debug(beginval);
	debug(seg);
	debug(vt);
	for (auto down : beginval) {
		f(i, 1, n)if (min(seg[i].first, seg[i].second) == down) {
			LL = i; break;
		}
		rf(i, n, 1)if (max(seg[i].first, seg[i].second) == down + len - 1) {
			RR = i; break;
		}
		vector<int> w(n + 1);
		f(i, 1, n)if (min(seg[i].first, seg[i].second) == down)w[i] = 1;
		debug(down, w);
		int m = vt.size();
		f(i, 0, m - 2) {
			ll L = vt[i], R = vt[i + 1] - 1;
			if (L < down)continue;
			vector<bool> ok(n + 1);
			f(i, 1, n)if (min(seg[i].first, seg[i].second) <= L && R <= max(seg[i].first, seg[i].second))ok[i] = 1;
			if (L != R) {
				mat.init();
				f(i, 1, n)f(j, i, n)if (ok[i] && ok[j])mat.a[i][j] = 1;
				f(i, 1, n)if (seg[i].first > seg[i].second)mat.a[i][i] = 0;
				mat = power(mat, R - L);
				w = w * mat;
				debug(L, R, w);
			}
			if (R == down + len - 1)break;
			mat.init();
			f(i, 1, n)f(j, i, n)
				if (ok[i])
					if (min(seg[j].first, seg[j].second) <= R + 1 && R + 1 <= max(seg[j].first, seg[j].second))
						mat.a[i][j] = 1;
			f(i, 1, n)if (seg[i].first > seg[i].second)mat.a[i][i] = 0;
			w = w * mat;
			debug(R + 1, w);
		}
		f(i, 1, n)if (max(seg[i].first, seg[i].second) == down + len - 1)res += w[i] % mod;
	}
	cout << len << " " << res % mod;
#ifdef local
	int end = clock();
	//cout << '\n' << end - start << "ms";
#endif* /
}
```