1474_F. 1 2 3 4 ...
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].
```python
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)
        #debug(active,X)
        #debug(A)     
        if i<m-1:
            for j,c in enumerate(corners):
                if c==y:
                    if j%2: # top: j and j+1 in active
                        idx=active.index(j)
                        X[idx+2]+=X[idx]
                        active.pop(idx)
                        active.pop(idx)
                        X.pop(idx)
                        X.pop(idx)
                    else: # bottom
                        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:
            #debug(corners[starti:endi+1])
            X+=get_rep(corners[starti:endi+1])
    else:
        X=1-corners[-1]
    print(L,X % 998244353)


    




```