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].

Source: codeforces | Difficulty: VERY_HARD
Tags: Matrices

Dynamic programming

Mathematics


Solutions:
import sys, io, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in55.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def debug(*args):
		pass

def mexp(size, power):
	A = []
	for i in range(size):
		A.append([int(j <= i // 2 * 2) for j in range(size)])
	powers = {1: A}
	p = 1
	while p * 2 <= power:
		powers[p * 2] = mmmult(powers[p], powers[p])
		p *= 2
	A = powers[p]
	power -= p
	while power > 0:
		p = p // 2
		if p <= power:
			A = mmmult(A, powers[p])
			power -= p
	return A

def mvmult(A, V):
	res = []
	for i in range(len(A)):
		res.append(sum((a * v for (a, v) in zip(A[i], V))) % 998244353)
	return res

def mmmult(A, B):
	res = []
	for i in range(len(A)):
		res.append([sum((a * B[j][k] for (j, a) in enumerate(A[i]))) for k in range(len(B[0]))])
	return res

def get_rep(corners):
	corners[0] -= 1
	corners[-1] += 1
	bps = sorted(list(set(corners)))
	m = len(bps)
	X = [1]
	active = [1]
	for i in range(1, m):
		(x, y) = (bps[i - 1], bps[i])
		d = y - x
		A = mexp(len(active), d)
		X = mvmult(A, X)
		if i < m - 1:
			for (j, c) in enumerate(corners):
				if c == y:
					if j % 2:
						idx = active.index(j)
						X[idx + 2] += X[idx]
						active.pop(idx)
						active.pop(idx)
						X.pop(idx)
						X.pop(idx)
					else:
						active += [j, j + 1]
						active.sort()
						idx = active.index(j)
						X = X[:idx] + [0, X[idx - 1]] + X[idx:]
		else:
			return X[0]
n = int(inp())
inp()
(d, *D) = map(int, inp().split())
if d == 0 and all((dd == 0 for dd in D)):
	print(1, 1)
else:
	while d == 0:
		(d, *D) = D
	up = d >= 0
	corners = [0, d]
	for d in D:
		x = corners[-1] + d
		if up == (d >= 0):
			corners[-1] = x
		if up != (d >= 0):
			up = d >= 0
			corners.append(x)
	debug(corners)
	cands = [(-1, 0, 0)]
	low = (0, 0)
	maxdiff = (0, 0, 0)
	for (i, corner) in enumerate(corners):
		if corner < low[0]:
			low = (corner, i)
		if corner - low[0] >= cands[0][0]:
			if corner - low[0] == cands[0][0] and low[1] > cands[0][1]:
				cands += [(corner - low[0], low[1], i)]
			else:
				cands = [(corner - low[0], low[1], i)]
	L = cands[0][0] + 1
	if L > 1:
		X = 0
		debug(cands)
		for (_, starti, endi) in cands:
			X += get_rep(corners[starti:endi + 1])
	else:
		X = 1 - corners[-1]
	print(L, X % 998244353)