#include <bits/stdc++.h>
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
constexpr int P = 998244353;
int add(int x, int y) {
	return (x + y < P) ? (x + y) : (x + y - P);
}
int mul(int x, int y) {
	return 1ll * x * y % P;
}
std::vector<i64> binpow(int len, i64 deg) {
	if (deg == 1) {
		return std::vector<i64>(len, 1);
	} else {
		std::vector<i64> pt = binpow(len, deg / 2);
		std::vector<i64> wle(len);
		auto D = [&](int i, int j) {
			if (i % 2 == 0) {
				return pt[j - i] % P;
			} else {
				return (j - i - 1 >= 0 ? pt[j - i - 1] % P : 0);
			}
		};
		for (int j = 0; j < len; j++) {
			for (int i = 0; i <= j; i++) {
				wle[j] = add(wle[j], mul(D(0, i), D(i, j)));
			}
		}
		if (deg & 1) {
			std::vector<i64> wle2(len);
			for (int j = 0; j < len; j++) {
				for (int i = 0; i <= j; i++) {
					if (i != j || j % 2 == 0) {
						wle2[j] = add(wle2[j], wle[i]);
					}
				}
			}
			return wle2;
		}
		return wle;
	}
}
void st(std::vector<i64> &dp, std::vector<i64> &ll, std::vector<i64> &rr, std::vector<i64> &fl, i64 z) {
	std::vector<i64> dp2(dp.size());
	for (int i = 0; i < (int)dp.size(); i++) {
		for (int j = 0; j < i + (fl[i] == 1); j++) {
			if (ll[i] <= z && z <= rr[i] && ll[j] <= z - 1 && z - 1 <= rr[j]) {
				dp2[i] = add(dp2[i], dp[j]);
			}
		}
	}
	dp = dp2;
}
int solve(std::vector<i64> v) {
	int sz = (int)v.size() - 1;
	std::vector<i64> ll(sz);
	std::vector<i64> rr(sz);
	std::vector<i64> fl(sz, 1);
	for (int i = 0; i < sz; i++) {
		ll[i] = v[i];
		rr[i] = v[i + 1];
		if (i) {
			if (ll[i] < rr[i]) {
				++ll[i];
			} else {
				--ll[i];
			}
		}
		if (ll[i] > rr[i]) {
			std::swap(ll[i], rr[i]);
			fl[i] = -1;
		}
	}
	std::vector<i64> dp(sz);
	std::sort(v.begin(), v.end());
	i64 fr = v[0];
	i64 to = v.back();
	for (int i = 0; i < sz; i++) {
		if (ll[i] <= fr && fr <= rr[i]) {
			dp[i] = 1;
		}
	}
	i64 lst = fr;
	for (auto p : v) {
		i64 z = p - 2;
		if (lst < z) {
			i64 d = z - lst;
			std::vector<int> act(sz);
			for (int i = 0; i < sz; i++) {
				for (int j = 0; j < i + (fl[i] == 1); j++) {
					if (ll[i] <= z && z <= rr[i] && ll[j] <= z && z <= rr[j]) {
						act[i] = act[j] = 1;
					}
				}
			}
			int cnt = 0;
			std::vector<int> lk(sz);
			for (int i = 0; i < sz; i++) {
				if (act[i]) {
					lk[i] = cnt++;
				}
			}
			std::vector<i64> fst = binpow(cnt, d);
			std::vector<i64> dp2(sz);
			auto D = [&](int i, int j) {
				if (i % 2 == 0) {
					return fst[j - i] % P;
				} else {
					return (j - i - 1 >= 0 ? fst[j - i - 1] % P : 0);
				}
			};
			for (int i = 0; i < sz; i++) {
				for (int j = 0; j <= i; j++) {
					dp2[i] = add(dp2[i], mul(dp[j], D(lk[j], lk[i])));
				}
			}
			dp = dp2;
			lst = z;
		}
		z = p - 1;
		if (lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
		z = p;
		if (lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
		z = p + 1;
		if (z <= to && lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
	}
	int res = 0;
	for (int i = 0; i < sz; i++) {
		if (ll[i] <= to && to <= rr[i]) {
			res = add(res, dp[i]);
		}
	}
	return res;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, t;
	std::cin >> n >> t;
	auto sgn = [&](i64 x) {
		if (x > 0) {
			return 1;
		} else if (x < 0) {
			return -1;
		} else {
			return 0;
		}
	};
	std::vector<i64> a;
	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		if (x == 0) {
			continue;
		}
		if (a.empty()) {
			a.emplace_back(x);
			continue;
		}
		if (sgn(x) == sgn(a.back())) {
			a.back() += x;
		} else {
			a.emplace_back(x);
		}
	}
	n = (int)a.size();
	std::vector<i64> s = {1};
	for (int i = 0; i < n; i++) {
		s.emplace_back(s.back() + a[i]);
	}
	i64 maxlen = 1;
	i64 mn = 1e18;
	for (int i = 0; i < (int)s.size(); i++) {
		mn = std::min(mn, s[i]);
		maxlen = std::max(maxlen, s[i] - mn + 1);
	}
	std::cout << maxlen << " ";
	if (maxlen == 1) {
		int ans = 1;
		for (int i = 0; i < (int)a.size(); i++) {
			ans = add(ans, std::abs(a[i]) % P);
		}
		std::cout << ans << "\n";
	} else {
		n = (int)s.size();
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int id = -1;
			for (int j = i + 1; j < n; j++) {
				if (s[j] - s[i] + 1 == maxlen) {
					id = j;
				}
			}
			if (id == -1) {
				continue;
			} else {
				std::vector<i64> ii;
				for (int j = i; j <= id; j++) {
					ii.emplace_back(s[j]);
				}
				i = id - 1;
				ans = add(ans, solve(ii));
			}
		}
		std::cout << ans << "\n";
	}
	return 0;
}

### Prompt

Create a solution in Cpp for 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
#include <bits/stdc++.h>
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
constexpr int P = 998244353;
int add(int x, int y) {
	return (x + y < P) ? (x + y) : (x + y - P);
}
int mul(int x, int y) {
	return 1ll * x * y % P;
}
std::vector<i64> binpow(int len, i64 deg) {
	if (deg == 1) {
		return std::vector<i64>(len, 1);
	} else {
		std::vector<i64> pt = binpow(len, deg / 2);
		std::vector<i64> wle(len);
		auto D = [&](int i, int j) {
			if (i % 2 == 0) {
				return pt[j - i] % P;
			} else {
				return (j - i - 1 >= 0 ? pt[j - i - 1] % P : 0);
			}
		};
		for (int j = 0; j < len; j++) {
			for (int i = 0; i <= j; i++) {
				wle[j] = add(wle[j], mul(D(0, i), D(i, j)));
			}
		}
		if (deg & 1) {
			std::vector<i64> wle2(len);
			for (int j = 0; j < len; j++) {
				for (int i = 0; i <= j; i++) {
					if (i != j || j % 2 == 0) {
						wle2[j] = add(wle2[j], wle[i]);
					}
				}
			}
			return wle2;
		}
		return wle;
	}
}
void st(std::vector<i64> &dp, std::vector<i64> &ll, std::vector<i64> &rr, std::vector<i64> &fl, i64 z) {
	std::vector<i64> dp2(dp.size());
	for (int i = 0; i < (int)dp.size(); i++) {
		for (int j = 0; j < i + (fl[i] == 1); j++) {
			if (ll[i] <= z && z <= rr[i] && ll[j] <= z - 1 && z - 1 <= rr[j]) {
				dp2[i] = add(dp2[i], dp[j]);
			}
		}
	}
	dp = dp2;
}
int solve(std::vector<i64> v) {
	int sz = (int)v.size() - 1;
	std::vector<i64> ll(sz);
	std::vector<i64> rr(sz);
	std::vector<i64> fl(sz, 1);
	for (int i = 0; i < sz; i++) {
		ll[i] = v[i];
		rr[i] = v[i + 1];
		if (i) {
			if (ll[i] < rr[i]) {
				++ll[i];
			} else {
				--ll[i];
			}
		}
		if (ll[i] > rr[i]) {
			std::swap(ll[i], rr[i]);
			fl[i] = -1;
		}
	}
	std::vector<i64> dp(sz);
	std::sort(v.begin(), v.end());
	i64 fr = v[0];
	i64 to = v.back();
	for (int i = 0; i < sz; i++) {
		if (ll[i] <= fr && fr <= rr[i]) {
			dp[i] = 1;
		}
	}
	i64 lst = fr;
	for (auto p : v) {
		i64 z = p - 2;
		if (lst < z) {
			i64 d = z - lst;
			std::vector<int> act(sz);
			for (int i = 0; i < sz; i++) {
				for (int j = 0; j < i + (fl[i] == 1); j++) {
					if (ll[i] <= z && z <= rr[i] && ll[j] <= z && z <= rr[j]) {
						act[i] = act[j] = 1;
					}
				}
			}
			int cnt = 0;
			std::vector<int> lk(sz);
			for (int i = 0; i < sz; i++) {
				if (act[i]) {
					lk[i] = cnt++;
				}
			}
			std::vector<i64> fst = binpow(cnt, d);
			std::vector<i64> dp2(sz);
			auto D = [&](int i, int j) {
				if (i % 2 == 0) {
					return fst[j - i] % P;
				} else {
					return (j - i - 1 >= 0 ? fst[j - i - 1] % P : 0);
				}
			};
			for (int i = 0; i < sz; i++) {
				for (int j = 0; j <= i; j++) {
					dp2[i] = add(dp2[i], mul(dp[j], D(lk[j], lk[i])));
				}
			}
			dp = dp2;
			lst = z;
		}
		z = p - 1;
		if (lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
		z = p;
		if (lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
		z = p + 1;
		if (z <= to && lst < z) {
			st(dp, ll, rr, fl, z);
			lst = z;
		}
	}
	int res = 0;
	for (int i = 0; i < sz; i++) {
		if (ll[i] <= to && to <= rr[i]) {
			res = add(res, dp[i]);
		}
	}
	return res;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, t;
	std::cin >> n >> t;
	auto sgn = [&](i64 x) {
		if (x > 0) {
			return 1;
		} else if (x < 0) {
			return -1;
		} else {
			return 0;
		}
	};
	std::vector<i64> a;
	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		if (x == 0) {
			continue;
		}
		if (a.empty()) {
			a.emplace_back(x);
			continue;
		}
		if (sgn(x) == sgn(a.back())) {
			a.back() += x;
		} else {
			a.emplace_back(x);
		}
	}
	n = (int)a.size();
	std::vector<i64> s = {1};
	for (int i = 0; i < n; i++) {
		s.emplace_back(s.back() + a[i]);
	}
	i64 maxlen = 1;
	i64 mn = 1e18;
	for (int i = 0; i < (int)s.size(); i++) {
		mn = std::min(mn, s[i]);
		maxlen = std::max(maxlen, s[i] - mn + 1);
	}
	std::cout << maxlen << " ";
	if (maxlen == 1) {
		int ans = 1;
		for (int i = 0; i < (int)a.size(); i++) {
			ans = add(ans, std::abs(a[i]) % P);
		}
		std::cout << ans << "\n";
	} else {
		n = (int)s.size();
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int id = -1;
			for (int j = i + 1; j < n; j++) {
				if (s[j] - s[i] + 1 == maxlen) {
					id = j;
				}
			}
			if (id == -1) {
				continue;
			} else {
				std::vector<i64> ii;
				for (int j = i; j <= id; j++) {
					ii.emplace_back(s[j]);
				}
				i = id - 1;
				ans = add(ans, solve(ii));
			}
		}
		std::cout << ans << "\n";
	}
	return 0;
}

```