//In the name of god
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define f first
#define s second
const int nax=1e5+100,mod=998244353;
int f[nax],invf[nax],fibo[nax];
int mul(int x,int y)
{
    return x*y%mod;
}
int expo(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
        res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}
int inv(int x)
{
    return expo(x,mod-2);
}
void init()
{
    f[0]=1;
    for(int i=1;i<nax;i++)
    f[i]=mul(f[i-1],i);
    invf[nax-1]=inv(f[nax-1]);
    for(int i=nax-1;i;i--)
    invf[i-1]=mul(invf[i],i);
}
int nck(int n,int r)
{
    if(r<0 or n<0 or r>n)
    return 0;
    return mul(f[n],mul(invf[r],invf[n-r]));
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    init();
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        vector<int> x(1);
        cin>>x[0];
        for(int i=0;i<n;i++)
        {
            int d;
            cin>>d;
            if(d!=0)
            x.push_back(x.back()+d);//since changes done at lst position
        }
        int res=0;
        n=x.size();
        vector<int> len(n);
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            len[i]=max(len[i],x[j]-x[i]+1);//all possible differences upto i
            res=max(res,len[i]);
        }
        if(res==1)//array with some common elements
        {
            cout<<"1 "<<(x[0]-x[n-1]+1)%mod<<'\n';
            return 0;
        }
        auto query=[&](vector<int> x)->int
        {
            int n=x.size();
            vector<bool> vis(n);
            vector<tuple<int,int,bool>> e(n);
            //take both possiblities for lcs
            e.emplace_back(x[0],0,1);
            e.emplace_back(x[0]+1,0,0);
            for(int i=1;i<n;i++)
            {
                if(x[i-1]<x[i])
                {
                    vis[i]=1;
                    e.emplace_back(x[i-1]+1,i,1);
                    e.emplace_back(x[i]+1,i,0);
                }
                else
                {
                    e.emplace_back(x[i],i,1);
                    e.emplace_back(x[i-1],i,0);
                }
            }
            sort(e.begin(),e.end());//e having all the lcs with and without changes are perform
            int lst=x[0]+1;
            vector<bool> mark(n);
            vector<int> dp(n);//for finding the length of lcs
            for(int i=0;i<n;i++)
            if(x[i]==x[0])
            dp[i]=1;
            for(auto it:e)
            {
                int v=get<0>(it);
                int i=get<1>(it);
                int t=get<2>(it);
                v=min(max(x[0]+1,v),x[0]+res);
                int times=v-lst;
                if(times==0)
                {
                    mark[i]=t;
                    continue;
                }
                times--;
                vector<vector<int>> cc(n+1,vector<int>(n+1));//to know the for all (j-i)
                for(int i=0;i<=n;i++)
                {
                    cc[i][0]=1;
                    for(int j=1;j<=n;j++)
                    cc[i][j]=mul(cc[i][j-1],(times%mod-i+j+mod));
                    //cc[i][j]%=mod;
                }
                for(int i=n-1;i>=0;i--)
                {
                    //depend on inclusion or exclusion operations dp changes
                    if(!mark[i])
                    {
                        dp[i]=0;
                        continue;
                    }
                    int newdp=0;
                    for(int j=0;j<=i;j++)
                    {
                        int a=0,b=0;
                        for(int k=j;k<=i;k++)
                        {
                            if(mark[k])
                            {
                                if(vis[k])
                                b++;
                                else
                                {
                                    a++;
                                    if(k==i)//to get the maximum lcs for the current i
                                    a--;
                                    if(k==j)//to get the maximum lcs for the current j
                                    a--;
                                }
                            }
                        }
                        int coef=0;
                        for(int k=0;k<=a and k<=times;k++)
                        coef=(coef+(nck(a,k)%mod*(b==0?(k==times):(cc[k][b-1]%mod*invf[b-1]%mod)))%mod)%mod;//varies as per the operations but should be positive
                        assert(coef>=0);
                        newdp=(newdp+mul(dp[j],coef))%mod;
                    }
                    dp[i]=newdp;
                }
                lst=v;
                mark[i]=t;
            }
            int ans=0;
            for(int i=0;i<n;i++)
            ans=(ans+dp[i])%mod;
            return ans;
        };
        //for every i do the querty to get highest lcs for each subsequence 
        int w=0,lst=-1,val=1e18;
        for(int i=0;i<n;i++)
        {
            if(len[i]==res and x[i]<val)
            {
                if(lst!=-1)
                w=(w+query(vector<int>(x.begin()+lst,x.begin()+i)))%mod;
                lst=i;
                val=x[i];
            }
        }
        w=(w+query(vector<int>(x.begin()+lst,x.begin()+n)))%mod;
        cout<<res<<' '<<w;
    }
    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
//In the name of god
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define f first
#define s second
const int nax=1e5+100,mod=998244353;
int f[nax],invf[nax],fibo[nax];
int mul(int x,int y)
{
    return x*y%mod;
}
int expo(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
        res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}
int inv(int x)
{
    return expo(x,mod-2);
}
void init()
{
    f[0]=1;
    for(int i=1;i<nax;i++)
    f[i]=mul(f[i-1],i);
    invf[nax-1]=inv(f[nax-1]);
    for(int i=nax-1;i;i--)
    invf[i-1]=mul(invf[i],i);
}
int nck(int n,int r)
{
    if(r<0 or n<0 or r>n)
    return 0;
    return mul(f[n],mul(invf[r],invf[n-r]));
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    init();
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        vector<int> x(1);
        cin>>x[0];
        for(int i=0;i<n;i++)
        {
            int d;
            cin>>d;
            if(d!=0)
            x.push_back(x.back()+d);//since changes done at lst position
        }
        int res=0;
        n=x.size();
        vector<int> len(n);
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            len[i]=max(len[i],x[j]-x[i]+1);//all possible differences upto i
            res=max(res,len[i]);
        }
        if(res==1)//array with some common elements
        {
            cout<<"1 "<<(x[0]-x[n-1]+1)%mod<<'\n';
            return 0;
        }
        auto query=[&](vector<int> x)->int
        {
            int n=x.size();
            vector<bool> vis(n);
            vector<tuple<int,int,bool>> e(n);
            //take both possiblities for lcs
            e.emplace_back(x[0],0,1);
            e.emplace_back(x[0]+1,0,0);
            for(int i=1;i<n;i++)
            {
                if(x[i-1]<x[i])
                {
                    vis[i]=1;
                    e.emplace_back(x[i-1]+1,i,1);
                    e.emplace_back(x[i]+1,i,0);
                }
                else
                {
                    e.emplace_back(x[i],i,1);
                    e.emplace_back(x[i-1],i,0);
                }
            }
            sort(e.begin(),e.end());//e having all the lcs with and without changes are perform
            int lst=x[0]+1;
            vector<bool> mark(n);
            vector<int> dp(n);//for finding the length of lcs
            for(int i=0;i<n;i++)
            if(x[i]==x[0])
            dp[i]=1;
            for(auto it:e)
            {
                int v=get<0>(it);
                int i=get<1>(it);
                int t=get<2>(it);
                v=min(max(x[0]+1,v),x[0]+res);
                int times=v-lst;
                if(times==0)
                {
                    mark[i]=t;
                    continue;
                }
                times--;
                vector<vector<int>> cc(n+1,vector<int>(n+1));//to know the for all (j-i)
                for(int i=0;i<=n;i++)
                {
                    cc[i][0]=1;
                    for(int j=1;j<=n;j++)
                    cc[i][j]=mul(cc[i][j-1],(times%mod-i+j+mod));
                    //cc[i][j]%=mod;
                }
                for(int i=n-1;i>=0;i--)
                {
                    //depend on inclusion or exclusion operations dp changes
                    if(!mark[i])
                    {
                        dp[i]=0;
                        continue;
                    }
                    int newdp=0;
                    for(int j=0;j<=i;j++)
                    {
                        int a=0,b=0;
                        for(int k=j;k<=i;k++)
                        {
                            if(mark[k])
                            {
                                if(vis[k])
                                b++;
                                else
                                {
                                    a++;
                                    if(k==i)//to get the maximum lcs for the current i
                                    a--;
                                    if(k==j)//to get the maximum lcs for the current j
                                    a--;
                                }
                            }
                        }
                        int coef=0;
                        for(int k=0;k<=a and k<=times;k++)
                        coef=(coef+(nck(a,k)%mod*(b==0?(k==times):(cc[k][b-1]%mod*invf[b-1]%mod)))%mod)%mod;//varies as per the operations but should be positive
                        assert(coef>=0);
                        newdp=(newdp+mul(dp[j],coef))%mod;
                    }
                    dp[i]=newdp;
                }
                lst=v;
                mark[i]=t;
            }
            int ans=0;
            for(int i=0;i<n;i++)
            ans=(ans+dp[i])%mod;
            return ans;
        };
        //for every i do the querty to get highest lcs for each subsequence 
        int w=0,lst=-1,val=1e18;
        for(int i=0;i<n;i++)
        {
            if(len[i]==res and x[i]<val)
            {
                if(lst!=-1)
                w=(w+query(vector<int>(x.begin()+lst,x.begin()+i)))%mod;
                lst=i;
                val=x[i];
            }
        }
        w=(w+query(vector<int>(x.begin()+lst,x.begin()+n)))%mod;
        cout<<res<<' '<<w;
    }
    return 0;
}
```