#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <chrono>
#include <array>
typedef long long ll;
typedef long double ld;
using namespace std;

const ll mod = 998244353;
const int maxn = 79;
void upd(ll& a, const ll& b)
{
    a += b;
    if (a >= mod) a -= mod;
}
ll pwr(ll a, ll b)
{
    if (!b) return 1;
    ll h = pwr(a, b >> 1);
    h = (h * h) % mod;
    if (b & 1) h = (h * a) % mod;
    return h;
}
int n; ll x;
vector<ll> d(maxn), s, inv(maxn * maxn, 1), l(maxn), r(maxn);
vector<int> p;
ll nck(ll n, ll k) // idealne pre male k a velke n
{
    if (k > n || k < 0) return 0;
    ll ans = 1;
    for (ll i = 0; i < k; i++) ans = (ans * (((n - i) * inv[i + 1]) % mod)) % mod;
    //cout << "C(" << n << ", " << k << ") = " << ans << "\n";
    return ans;
}
ll split(ll n, ll k) // tak ako je ta analogia s rozdelovacmi
{
    if (k == 0) return 1;
    return nck(n + k - 1, k - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i < inv.size(); i++) inv[i] = pwr(i, mod - 2);
    cin >> n >> x;
    bool dec = true;
    for (int i = 0; i < n; i++)
    {
        cin >> d[i];
        if (d[i] > 0) dec = false;
        l[i] = (i ? r[i - 1] : x);
        r[i] = l[i] + d[i];
        s.push_back(l[i]), s.push_back(r[i]);
    }
    if (dec)
    {
        cout << 1 << " " << (x - r[n - 1] + 1) % mod << "\n";
        return 0;
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for (int i = 0; i < n; i++)
    {
        int idl = -1, idr = -1; // idl tam uz dala ta predosla cesta, ten sa nerata
        for (int j = 0; j < s.size(); j++)
        {
            if (s[j] == l[i]) idl = j;
            if (s[j] == r[i]) idr = j;
        }
        if (i == 0) p.push_back(idl);
        if (idl < idr) for (int j = idl + 1; j <= idr; j++) p.push_back(j);
        else for (int j = idl - 1; j >= idr; j--) p.push_back(j);
    }
    ll len = 0, ans = 0; int m = p.size();
    for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) if (p[i] < p[j]) len = max(len, s[p[j]] - s[p[i]] + 1);
    vector<vector<ll> > ways(m, vector<ll>(m, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = i + 1; j < m; j++)
        {
            if (p[i] + 1 != p[j]) continue;
            int up = 0, dw = 0;
            ll need = s[p[j]] - s[p[i]] - 1; // prvy a posledny prvok su uz zafixovane
            for (int k = i; k < j; k++)
            {
                if (p[k] == p[i] && p[k + 1] == p[j]) up++;
                if (p[k] == p[j] && p[k + 1] == p[i]) dw++;
            }
            for (int use = 0; use <= min((ll)dw, need); use++)
                upd(ways[i][j], (split(need - use, up) * nck(dw, use)) % mod);
            //cout << i << " " << j << " : " << ways[i][j] << " (" << up << ", " << dw << ")\n";
        }
    }
    for (int i = 0; i < s.size(); i++)
    {
        vector<ll> dp(m, 0); // pre kazdy prvok si pamatame, ze kolko sposobov mame, ako urobit optimalnu lis, ak chceme zacat na prvku s hodnotou s[i]s
        for (int j = 0; j < m; j++) if (p[j] == i) dp[j] = 1;
        for (int j = 0; j < m; j++) for (int k = j + 1; k < m; k++) upd(dp[k], (dp[j] * ways[j][k]) % mod);
        //for (int j = 0; j < m; j++) cout << dp[j] << " ";
        //cout << "\n";
        for (int j = 0; j < m; j++) if (s[p[j]] - s[i] + 1 == len) upd(ans, dp[j]);
    }
    cout << len << " " << ans << "\n";
    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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <chrono>
#include <array>
typedef long long ll;
typedef long double ld;
using namespace std;

const ll mod = 998244353;
const int maxn = 79;
void upd(ll& a, const ll& b)
{
    a += b;
    if (a >= mod) a -= mod;
}
ll pwr(ll a, ll b)
{
    if (!b) return 1;
    ll h = pwr(a, b >> 1);
    h = (h * h) % mod;
    if (b & 1) h = (h * a) % mod;
    return h;
}
int n; ll x;
vector<ll> d(maxn), s, inv(maxn * maxn, 1), l(maxn), r(maxn);
vector<int> p;
ll nck(ll n, ll k) // idealne pre male k a velke n
{
    if (k > n || k < 0) return 0;
    ll ans = 1;
    for (ll i = 0; i < k; i++) ans = (ans * (((n - i) * inv[i + 1]) % mod)) % mod;
    //cout << "C(" << n << ", " << k << ") = " << ans << "\n";
    return ans;
}
ll split(ll n, ll k) // tak ako je ta analogia s rozdelovacmi
{
    if (k == 0) return 1;
    return nck(n + k - 1, k - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i < inv.size(); i++) inv[i] = pwr(i, mod - 2);
    cin >> n >> x;
    bool dec = true;
    for (int i = 0; i < n; i++)
    {
        cin >> d[i];
        if (d[i] > 0) dec = false;
        l[i] = (i ? r[i - 1] : x);
        r[i] = l[i] + d[i];
        s.push_back(l[i]), s.push_back(r[i]);
    }
    if (dec)
    {
        cout << 1 << " " << (x - r[n - 1] + 1) % mod << "\n";
        return 0;
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for (int i = 0; i < n; i++)
    {
        int idl = -1, idr = -1; // idl tam uz dala ta predosla cesta, ten sa nerata
        for (int j = 0; j < s.size(); j++)
        {
            if (s[j] == l[i]) idl = j;
            if (s[j] == r[i]) idr = j;
        }
        if (i == 0) p.push_back(idl);
        if (idl < idr) for (int j = idl + 1; j <= idr; j++) p.push_back(j);
        else for (int j = idl - 1; j >= idr; j--) p.push_back(j);
    }
    ll len = 0, ans = 0; int m = p.size();
    for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) if (p[i] < p[j]) len = max(len, s[p[j]] - s[p[i]] + 1);
    vector<vector<ll> > ways(m, vector<ll>(m, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = i + 1; j < m; j++)
        {
            if (p[i] + 1 != p[j]) continue;
            int up = 0, dw = 0;
            ll need = s[p[j]] - s[p[i]] - 1; // prvy a posledny prvok su uz zafixovane
            for (int k = i; k < j; k++)
            {
                if (p[k] == p[i] && p[k + 1] == p[j]) up++;
                if (p[k] == p[j] && p[k + 1] == p[i]) dw++;
            }
            for (int use = 0; use <= min((ll)dw, need); use++)
                upd(ways[i][j], (split(need - use, up) * nck(dw, use)) % mod);
            //cout << i << " " << j << " : " << ways[i][j] << " (" << up << ", " << dw << ")\n";
        }
    }
    for (int i = 0; i < s.size(); i++)
    {
        vector<ll> dp(m, 0); // pre kazdy prvok si pamatame, ze kolko sposobov mame, ako urobit optimalnu lis, ak chceme zacat na prvku s hodnotou s[i]s
        for (int j = 0; j < m; j++) if (p[j] == i) dp[j] = 1;
        for (int j = 0; j < m; j++) for (int k = j + 1; k < m; k++) upd(dp[k], (dp[j] * ways[j][k]) % mod);
        //for (int j = 0; j < m; j++) cout << dp[j] << " ";
        //cout << "\n";
        for (int j = 0; j < m; j++) if (s[p[j]] - s[i] + 1 == len) upd(ans, dp[j]);
    }
    cout << len << " " << ans << "\n";
    return 0;
}
```