#include "bits/stdc++.h"
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 50
#define mod 998244353
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

typedef array<array<int,55>,55> mat;
int mat_n;

mat operator *(const mat &A,const mat &B)
{
    mat C{};
    rep(i,1,mat_n) rep(k,1,mat_n) rep(j,1,mat_n) C[i][j]=(C[i][j]+1ll*A[i][k]*B[k][j])%mod;
    return C;
}

mat qp(mat A,ll k)
{
    mat res{}; rep(i,1,mat_n) res[i][i]=1;
    while(k)
    {
        if(k&1) res=res*A;
        A=A*A;
        k>>=1;
    }
    return res;
}

int N;
ll d[maxn+5],a[maxn+5];

ll cal(vector<ll> a)
{
    int n=a.size()-1;
    assert(n&1);
    a[0]=-1;
    vector<ll> vec;
    rep(i,1,n) 
    {
        if(i&1) 
        {
            vec.pb(a[i-1]+1);
            vec.pb(a[i]+1);
        }
        else
        {
            vec.pb(a[i-1]);
            vec.pb(a[i]);
        }
    }
    sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());
    int N=vec.size();
    mat_n=n;
    mat A{}; rep(i,1,n) A[i][i]=1;
    rep(id,0,N-2)
    {
        ll x=vec[id];
        mat B{};
        rep(i,1,n)
        {
            if(i&1 && a[i-1]+1<=x && x<=a[i])
            {
                rep(j,1,i) B[i][j]=1;
            }
            if((i&1)==0 && a[i]<=x && x<=a[i-1]-1)
            {
                rep(j,1,i-1) B[i][j]=1;
            }
        }
        A=qp(B,vec[id+1]-x)*A;
    }
    ll ans=0;
    rep(i,1,n) ans=(ans+A[i][1])%mod;
    return ans;
}

int main()
{
    int n,x; scanf("%d%d",&n,&x);
    rep(i,1,n)
    {
        int x; scanf("%d",&x);
        if(x!=0)
        {
            if((x>0 && d[N]>0) || (x<0 && d[N]<0)) d[N]+=x;
            else d[++N]=x;
        }
    }
    rep(i,0,N) a[i+1]=a[i]+d[i];
    n=N+1;
    ll MX=0;
    rep(i,1,n)
    {
        ll tmp=a[i];
        rep(j,i+1,n) tmp=max(tmp,a[j]);
        MX=max(MX,tmp-a[i]);
    }
    if(MX==0) return printf("1 %lld\n",(-a[n]+1)%mod),0;
    ll ans=0;
    rep(i,1,n)
    {
        int r=-1;
        rep(j,i+1,n) if(a[j]-a[i]==MX) r=j;
        if(r!=-1) 
        {
            vector<ll> b;
            rep(j,i,r) b.pb(a[j]-a[i]);
            ans=(ans+cal(b))%mod;    
            i=r;
        }
    }
    printf("%lld %lld\n",MX+1,ans);
    return 0;
}
### Prompt

Please create a solution in CPP to 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"
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 50
#define mod 998244353
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

typedef array<array<int,55>,55> mat;
int mat_n;

mat operator *(const mat &A,const mat &B)
{
    mat C{};
    rep(i,1,mat_n) rep(k,1,mat_n) rep(j,1,mat_n) C[i][j]=(C[i][j]+1ll*A[i][k]*B[k][j])%mod;
    return C;
}

mat qp(mat A,ll k)
{
    mat res{}; rep(i,1,mat_n) res[i][i]=1;
    while(k)
    {
        if(k&1) res=res*A;
        A=A*A;
        k>>=1;
    }
    return res;
}

int N;
ll d[maxn+5],a[maxn+5];

ll cal(vector<ll> a)
{
    int n=a.size()-1;
    assert(n&1);
    a[0]=-1;
    vector<ll> vec;
    rep(i,1,n) 
    {
        if(i&1) 
        {
            vec.pb(a[i-1]+1);
            vec.pb(a[i]+1);
        }
        else
        {
            vec.pb(a[i-1]);
            vec.pb(a[i]);
        }
    }
    sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());
    int N=vec.size();
    mat_n=n;
    mat A{}; rep(i,1,n) A[i][i]=1;
    rep(id,0,N-2)
    {
        ll x=vec[id];
        mat B{};
        rep(i,1,n)
        {
            if(i&1 && a[i-1]+1<=x && x<=a[i])
            {
                rep(j,1,i) B[i][j]=1;
            }
            if((i&1)==0 && a[i]<=x && x<=a[i-1]-1)
            {
                rep(j,1,i-1) B[i][j]=1;
            }
        }
        A=qp(B,vec[id+1]-x)*A;
    }
    ll ans=0;
    rep(i,1,n) ans=(ans+A[i][1])%mod;
    return ans;
}

int main()
{
    int n,x; scanf("%d%d",&n,&x);
    rep(i,1,n)
    {
        int x; scanf("%d",&x);
        if(x!=0)
        {
            if((x>0 && d[N]>0) || (x<0 && d[N]<0)) d[N]+=x;
            else d[++N]=x;
        }
    }
    rep(i,0,N) a[i+1]=a[i]+d[i];
    n=N+1;
    ll MX=0;
    rep(i,1,n)
    {
        ll tmp=a[i];
        rep(j,i+1,n) tmp=max(tmp,a[j]);
        MX=max(MX,tmp-a[i]);
    }
    if(MX==0) return printf("1 %lld\n",(-a[n]+1)%mod),0;
    ll ans=0;
    rep(i,1,n)
    {
        int r=-1;
        rep(j,i+1,n) if(a[j]-a[i]==MX) r=j;
        if(r!=-1) 
        {
            vector<ll> b;
            rep(j,i,r) b.pb(a[j]-a[i]);
            ans=(ans+cal(b))%mod;    
            i=r;
        }
    }
    printf("%lld %lld\n",MX+1,ans);
    return 0;
}
```