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>

using namespace std;

#define sz(a) int(a.size())
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;


template<int MOD>
struct ModInt {
	int n;
	ModInt(const ModInt<MOD> &v):n(v.n){ }
	ModInt():n(0){}
	ModInt(ll nn){
		if(nn < -MOD || nn >= MOD)nn %= MOD;
		if(nn < 0)nn += MOD;
		n = nn;
	}
	ModInt<MOD> operator+(const ModInt<MOD> &M)const{
		return ModInt::safe(n + M.n >= MOD ? (n + M.n - MOD) : (n + M.n));
	}
	ModInt<MOD> operator-(const ModInt<MOD> &M)const{
		return ModInt::safe(n >= M.n ? (n - M.n) : (n - M.n + MOD));
	}
	ModInt<MOD> operator*(const ModInt<MOD> &M)const{
		return ModInt::safe(((ll)n * M.n) % MOD);
	}
	ModInt<MOD> operator+=(const ModInt<MOD> &M) {
		return ModInt::safe(n = ((*this)+(M)).n);
	}
	ModInt<MOD> operator-=(const ModInt<MOD> &M) {
		return ModInt::safe(n = ((*this)-(M)).n);
	}
	ModInt<MOD> operator*=(const ModInt<MOD> &M) {
		return ModInt::safe(n = ((*this)*(M)).n);
	}
	inline static ModInt<MOD> safe(int n) {
		ModInt<MOD> m;
		m.n = n;
		return m;
	}
};
const int MOD = 998244353;
typedef ModInt<MOD> mint;

template<class T>
struct Matrix
{
	vector<T> MAT;
	int N,M;
	Matrix(int N,int M) : N(N), M(M), MAT(N * M) { }
	static Matrix<T> identity(int N) {
		Matrix<T> A(N, N);
		for(int i = 0; i < N; ++i) A(i, i) = 1;
		return A;
	}
	Matrix<T> operator+(const Matrix<T> &o) const {
		Matrix<T> A(N, M);
		for (int i = 0; i < N * M; ++i) A.MAT[i] = o.MAT[i] + MAT[i];
		return A;
	}
	Matrix<T> operator*(const Matrix<T> &o) const {
		Matrix<T> A(N , o.M);
		for(int i = 0; i < N; ++i) {
			for(int j = 0; j < o.M; ++j) { // careful with o.M
				for(int k = 0; k < M; ++k) {
					A.MAT[i * o.M + j] =
							(A.MAT[i * o.M + j] + MAT[i * M + k] * o.MAT[k * o.M + j]);
				}
			}
		}
		return A;
	}
	Matrix<T> pow(ll n) const {
		Matrix<T> A = identity(N), P = (*this);
		while(n) {
			if (n & 1) A = A * P;
			P = P * P;
			n /= 2;
		}
		return A;
	}
	T& operator()(int i, int j){ return MAT[i*M + j]; }
	string str() {
		stringstream st;
		st << "{\n";
		for(int i = 0; i < N; ++i) {
			st << "[";
			for(int j = 0; j < M; ++j) st << (j==0?"":" ") << (*this)(i, j);
			st << "]\n";
		}
		return st.str() + "}\n";
	}
};

vector <ll> compress (vector <ll> &d) {
	int n = sz(d);
	vector <ll> r;
	for (auto t : d) {
		if (t == 0) continue;
		if (!r.empty() && t < 0 == r.back() < 0) {
			r.back() += t;
			continue;
		}
		r.push_back(t);
	}
	return r;
}

void getPoints (vector <ll> &d, vector<ll> &Vx, vector<ll> &Vy) {
	Vx = {0}, Vy = {0};
	ll curX = 0, curY = 0;
	for (auto t : d) {
		curX += abs(t);
		curY += t;
		Vy.push_back(curY);
		Vx.push_back(curX);
	}
}

vector<ll> getPos(const vector<ll> &Vx, const vector <ll> &Vy, ll L) {
	int n = sz(Vx);
	vector<ll> Rx;
	if (L == Vy[0]) Rx.push_back(Vx[0]);
	for (int i = 1; i < n; ++i) {
		if (Vy[i-1] < L && L < Vy[i]) {
			Rx.push_back(Vx[i - 1] + L - Vy[i - 1]);
		}
		if (Vy[i] < L && L < Vy[i-1]) {
			Rx.push_back(Vx[i - 1] + Vy[i - 1] - L);
		}
		if (Vy[i] == L)
			Rx.push_back(Vx[i]);
	}
	return Rx;
}

VI computeNext(const vector<ll> &Vx, const vector <ll> &Vy, VI Cw, ll L) {
	vector<ll> cl = getPos(Vx, Vy, L), nl = getPos(Vx, Vy, L+1);
	VI W(nl.size());
	for (int i = 0; i < nl.size(); ++i) {
		for (int j = 0; j < cl.size(); ++j) {
			if (cl[j] < nl[i]) {
				W[i] += Cw[j];
				if (W[i] >= MOD) W[i] -= MOD;
			}
		}
	}
	return W;
}

Matrix<mint> getMatrix(const vector<ll> &Vx, const vector <ll> &Vy, ll a) {
	auto cl = getPos(Vx, Vy, a), nl = getPos(Vx, Vy, a+1);
	assert(sz(cl) == sz(nl));
	Matrix<mint> M(cl.size(), cl.size());
	for (int i = 0; i < nl.size(); ++i) {
		for (int j = 0; j < cl.size(); ++j) {
			if (cl[j] < nl[i]) {
				M(i, j) = 1;
			}
		}
	}
	return M;
}

VI goUp (const vector <ll> &Vx, const vector <ll> &Vy, VI W, ll a, ll b) {
	ll k = b-a;
	if (k == 1) {
		W = computeNext(Vx, Vy, W, a);
	} else {
		int n = sz(W);
		Matrix<mint> Mw (W.size(), 1);
		for (int i = 0; i < n; i++) Mw(i, 0) = W[i];
		auto m = getMatrix(Vx, Vy, a);
		auto o = m.pow(k) * Mw;
		for (int i = 0; i < n; i++) W[i] = o(i, 0).n;
	}
	return W;
}

int process (const vector<ll> & Vx, const vector<ll> &Vy) {
	set <ll> S (Vy.begin(), Vy.end());
	ll cy = *S.begin();
	S.erase(S.begin());

	VI W (sz(getPos(Vx, Vy, cy)), 1);

	for (auto y : S) {
		W = goUp(Vx, Vy, W, cy, cy+1);
		cy++;
		if (cy == y) continue;
		ll k = y-cy-1;
		if (k > 0) W = goUp(Vx, Vy, W, cy, y-1);

		W = goUp(Vx, Vy, W, y-1, y);
		cy = y;
	}

	mint ans = 0;
	for (int t : W) ans += t;
	return ans.n;
}

int main () {
	int n;
	cin >> n;

	int tr;
	scanf("%d", &tr);

	vector<ll> d (n);
	for (auto &t : d) {
		scanf("%lld", &t);
	}
	d = compress(d);
	n = sz(d);

	if (n == 0) {
		puts("1 1");
		return 0;
	}

	if ((n == 1 && d[0] < 0)) {
		cout << 1 << " " << (-d[0]+1)%MOD << endl;
		return 0;
	}

	vector <ll> Vx, Vy;
	getPoints(d, Vx, Vy);

	n = sz(Vx);

	vector<ll> L (n, 1);

	ll ML = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			L[i] = max(L[i], Vy[i]-Vy[j]+1);
		}
		ML = max(ML, L[i]);
	}

	mint ans = 0;
	for (int i = 0; i < n; i++) {
		int l = -1;
		for (int j = i; j < n; j++) {
			if (ML == Vy[j]-Vy[i]+1) l = j;
		}
		if (l != -1) {
			ans += process(
					vector<ll>(Vx.begin()+i, Vx.begin()+l+1),
			        vector<ll>(Vy.begin()+i, Vy.begin()+l+1)
			        );
			i = l;
		}
	}
	cout << ML << " " << ans.n << endl;
}