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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(v) int((v).size())
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define int ll
template<typename A,typename B>
string to_string(pair<A,B>p){return"("+to_string(p.first)+", "+to_string(p.second)+")";}
template<typename A,typename B,typename C>
string to_string(tuple<A,B,C>p){return"("+to_string(get<0>(p))+", "+to_string(get<1>(p))+", "+to_string(get<2>(p))+")";}
template<typename A,typename B,typename C,typename D>
string to_string(tuple<A,B,C,D>p){return"("+to_string(get<0>(p))+", "+to_string(get<1>(p))+", "+to_string(get<2>(p))+", "+to_string(get<3>(p))+")";}
string to_string(const string &s){return'"'+s+'"';}
string to_string(const char *s){return to_string((string)s);}
string to_string(bool b){return(b?"true":"false");}
string to_string(vector<bool>v){int f=0;string r="{";for(bool i:v)r+=(f++?",":"")+to_string(i);r+="}";return r;}
template<size_t N>
string to_string(bitset<N>v){string res="";for(size_t i=0;i<N;res+=char('0'+v[i++]));return res;}
template<typename A>
string to_string(A v){int f=0;string r="{";for(auto&i:v)r+=(f++?",":"")+to_string(i);r+="}";return r;}
void debug_out(){cerr<<']'<<endl;}
template<typename Head,typename...Tail>
void debug_out(Head H,Tail...T){cerr<<to_string(H);if(sizeof...(T))cerr<<", ";debug_out(T...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << (#x) << "] = [", debug_out(x)
#else
#define debug(x...) 33
#endif
const int mod = 998244353;
const int N = 51;
typedef array<array<int, N>, N> mat;
mat operator * (const mat& a, const mat& b)
{
    mat c;
    forn(i, N) forn(j, N) c[i][j] = 0;
    forn(i, N) forn(j, N) forn(k, N)
        c[i][j] = (c[i][j] + a[i][k] * b[k][j])%mod;
    return c;
}
mat power(mat a, int b)
{
    mat res;
    forn(i, N) forn(j, N) res[i][j] = (i == j);
    for(;b;b>>=1,a=a*a)
        if (b&1) res = res * a;
    return res;
}
int f(const vector<int>& a)
{
    int n = a.size();
    vector<pair<int, int>> segs;
    int x = 0;
    forn(i, n)
    {
        segs.push_back({x + (a[i] < 0 ? -1 : 1), x + a[i]});// 포함구간
        x += a[i];
    }
    segs[0].first = 0;//ok
    vector<int> qs;
    for (auto& it: segs)
    {
        for (int z = -1;z<=1;++z)// maybe just all check?
        {
            qs.push_back(it.first + z);
            qs.push_back(it.second + z);
        }
    }
    sort(all(qs));
    qs.resize(unique(all(qs))-qs.begin());
    qs.pop_back();//why? maybe just delete over the range (last peak + 1)
    debug(qs);
    vector<int> ans(n + 1);
    ans[0] = 1;
    int lst = -1;
    for (auto x: qs)
    {
        mat cur{};
        forn(i, n) if (min(segs[i].first, segs[i].second)<=lst + 1 && x <= max(segs[i].first, segs[i].second))
        {
            if (segs[i].first < segs[i].second)
                forn(j, i + 2) cur[j][i + 1] = 1;
            else
                forn(j, i + 1) cur[j][i + 1] = 1;
        }
        cur = power(cur, x - lst);
        vector<int> nxt_ans(n + 1);
        forn(i, n + 1) forn(j, n + 1)
            nxt_ans[j] = (nxt_ans[j] + ans[i] * cur[i][j]%mod)%mod;
        ans = nxt_ans;
        lst = x;
    }
    int sum = 0;
    forn(i, n + 1) sum = (sum + ans[i])%mod;
    return sum;
}
signed main(void)
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    int x; cin>>x;
    vector<int> a;
    forn(i, n)
    {
        int t; cin>>t;
        if (t) a.push_back(t);
    }
    n = sz(a);
    int mx = 0;
    forn(i, n)
    {
        int cur = 0;
        for (int j=i; j<n;++j)
        {
            cur += a[j];
            mx = max(mx, cur);
        }
    }
    if (mx == 0) // LLIS = 1, yes
    {
        int sum = 1;
        forn(i, n) sum = ( (sum - a[i])%mod + mod)%mod;
        cout << 1 << ' ' <<sum << '\n';
        return 0;
    }
    vector<pair<int, int>> bst;
    forn(i, n)
    {
        int cur = 0;
        int r = -1;
        for (int j = i; j < n;++j)
        {
            cur += a[j];
            if (mx == cur) r = j;
        }
        if (r!=-1)
        {
            bst.push_back({i, r});
            i = r;
        }
    }
    debug(bst);
    int sum = 0;
    for(auto& it: bst) sum = (sum + f(  vector<int>(a.begin() + it.first, a.begin()+it.second + 1) )   )%mod;
    cout << mx + 1 << ' ' <<sum << '\n';
    return 0;
}