#include <bits/stdc++.h>
using namespace std;

const int M = 998244353;
struct mint {

  int value;

  mint() : value(0) {}

  template <class T>
  mint(T x) {
    value = x % M;
    if (value < 0) {
      value += M;
    }
  }

  mint & operator++() {
    if (++value == M) {
      value = 0;
    }
    return *this;
  }

  mint & operator--() {
    if (--value == -1) {
      value = M - 1;
    }
    return *this;
  }

  mint operator++(int) {
    mint res = *this;
    ++*this;
    return res;
  }

  mint operator--(int) {
    mint res = *this;
    --*this;
    return res;
  }

  mint & operator+=(mint oth) {
    value += oth.value;
    if (value >= M) {
      value -= M;
    }
    return *this;
  }

  mint & operator-=(mint oth) {
    value -= oth.value;
    if (value < 0) {
      value += M;
    }
    return *this;
  }

  mint & operator*=(mint oth) {
    value = (long long) value * oth.value % M;
    return *this;
  }

  mint operator+() const {
    return *this;
  }

  mint operator-() const {
    return mint() - *this;
  }

  mint pow(long long e = M - 2) const {
    mint res = 1, b = *this;
    while (e > 0) {
      if (e % 2 == 1) {
        res *= b;
      }
      b *= b;
      e /= 2;
    }
    return res;
  }

  friend mint operator+(mint a, mint b) {
    return a += b;
  }

  friend mint operator-(mint a, mint b) {
    return a -= b;
  }

  friend mint operator*(mint a, mint b) {
    return mint(a) *= b;
  }

  friend bool operator==(mint a, mint b) {
    return a.value == b.value;
  }

  friend bool operator!=(mint a, mint b) {
    return a.value != b.value;
  }

  friend ostream & operator<<(ostream &out, mint a) {
    out << a.value;
    return out;
  }

};

const int N = 50 + 1;

long long peak[N];

mint evaluate(vector<array<mint, 2>> &f, mint x) {
  int degree = (int) f.size();
  mint res = 0;

  for (int i = 0; i < degree; ++i) {
    mint num = 1, den = 1;
    for (int j = 0; j < degree; ++j) {
      if (i != j) {
        num *= x - f[j][0];
        den *= f[i][0] - f[j][0];
      }
    }
    res += f[i][1] * num * den.pow();
  }

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x;
  cin >> n >> x;

  for (int i = 1; i <= n; ++i) {
    int d;
    cin >> d;
    peak[i] = peak[i - 1] + d;
  }

  long long length = 0;
  for (int i = 0; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      length = max(length, peak[j] - peak[i] + 1);
    }
  }

  if (length == 1) {
    cout << 1 << " " << mint(-peak[n] + 1) << "\n";
    exit(0);
  }

  mint ans = 0;
  for (int l = 0; l <= n; ++l) {
    int r = -1;
    for (int i = l; i <= n; ++i) {
      if (peak[i] - peak[l] + 1 == length) {
        r = i;
      }
    }

    if (r == -1) {
      continue;
    }

    map<long long, vector<array<mint, 2>>> ways;
    ways[peak[l] - 1] = {{0, 1}};
    ways[peak[l] + 1] = {};

    for (int i = l; i < r; ++i) {
      if (peak[i + 1] == peak[i]) {
        continue;
      }

      map<long long, vector<array<mint, 2>>> new_ways = ways;
      if (peak[i + 1] > peak[i]) {
        new_ways[peak[i] + 1] = (--ways.upper_bound(peak[i] + 1))->second;
        new_ways[peak[i + 1] + 1] = (--ways.upper_bound(peak[i + 1] + 1))->second;

        for (auto it = ++new_ways.begin(); it != new_ways.end(); ++it) {
          auto &[x, f] = *it;
          if (x > peak[i] && x <= peak[i + 1]) {
            auto prv = it, nxt = it;
            --prv, ++nxt;

            vector<array<mint, 2>> g;
            mint prefix = evaluate(prv->second, x - 1);
            for (long long y = x; y < min(x + N, nxt->first); ++y) {
              prefix += evaluate(f, y);
              g.push_back({y, prefix});
            }
            f = g;
          }
        }
      } else {
        new_ways[peak[i]] = (--ways.upper_bound(peak[i]))->second;
        new_ways[peak[i + 1]] = (--ways.upper_bound(peak[i + 1]))->second;

        for (auto &[x, f] : ways) {
          if (x >= peak[i + 1] && x < peak[i]) {
            if (new_ways.count(x + 1) == 0) {
              new_ways[x + 1] = f;
            }
          }
        }

        for (auto it = ++new_ways.begin(); it != new_ways.end(); ++it) {
          auto &[x, f] = *it;
          if (x >= peak[i + 1] && x < peak[i]) {
            auto prv = it, nxt = it;
            --prv, ++nxt;

            vector<array<mint, 2>> g;
            mint value = evaluate((--ways.lower_bound(x))->second, x - 1);
            for (long long y = x; y < min(x + N, nxt->first); ++y) {
              mint new_value = evaluate(f, y);
              g.push_back({y, value + new_value});
              value = new_value;
            }
            f = g;
          }
        }
      }
      swap(ways, new_ways);
    }

    ans += evaluate((--ways.upper_bound(peak[r]))->second, peak[r]);

    l = r;
  }

  cout << length << " " << ans << "\n";
}

### 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>
using namespace std;

const int M = 998244353;
struct mint {

  int value;

  mint() : value(0) {}

  template <class T>
  mint(T x) {
    value = x % M;
    if (value < 0) {
      value += M;
    }
  }

  mint & operator++() {
    if (++value == M) {
      value = 0;
    }
    return *this;
  }

  mint & operator--() {
    if (--value == -1) {
      value = M - 1;
    }
    return *this;
  }

  mint operator++(int) {
    mint res = *this;
    ++*this;
    return res;
  }

  mint operator--(int) {
    mint res = *this;
    --*this;
    return res;
  }

  mint & operator+=(mint oth) {
    value += oth.value;
    if (value >= M) {
      value -= M;
    }
    return *this;
  }

  mint & operator-=(mint oth) {
    value -= oth.value;
    if (value < 0) {
      value += M;
    }
    return *this;
  }

  mint & operator*=(mint oth) {
    value = (long long) value * oth.value % M;
    return *this;
  }

  mint operator+() const {
    return *this;
  }

  mint operator-() const {
    return mint() - *this;
  }

  mint pow(long long e = M - 2) const {
    mint res = 1, b = *this;
    while (e > 0) {
      if (e % 2 == 1) {
        res *= b;
      }
      b *= b;
      e /= 2;
    }
    return res;
  }

  friend mint operator+(mint a, mint b) {
    return a += b;
  }

  friend mint operator-(mint a, mint b) {
    return a -= b;
  }

  friend mint operator*(mint a, mint b) {
    return mint(a) *= b;
  }

  friend bool operator==(mint a, mint b) {
    return a.value == b.value;
  }

  friend bool operator!=(mint a, mint b) {
    return a.value != b.value;
  }

  friend ostream & operator<<(ostream &out, mint a) {
    out << a.value;
    return out;
  }

};

const int N = 50 + 1;

long long peak[N];

mint evaluate(vector<array<mint, 2>> &f, mint x) {
  int degree = (int) f.size();
  mint res = 0;

  for (int i = 0; i < degree; ++i) {
    mint num = 1, den = 1;
    for (int j = 0; j < degree; ++j) {
      if (i != j) {
        num *= x - f[j][0];
        den *= f[i][0] - f[j][0];
      }
    }
    res += f[i][1] * num * den.pow();
  }

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x;
  cin >> n >> x;

  for (int i = 1; i <= n; ++i) {
    int d;
    cin >> d;
    peak[i] = peak[i - 1] + d;
  }

  long long length = 0;
  for (int i = 0; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      length = max(length, peak[j] - peak[i] + 1);
    }
  }

  if (length == 1) {
    cout << 1 << " " << mint(-peak[n] + 1) << "\n";
    exit(0);
  }

  mint ans = 0;
  for (int l = 0; l <= n; ++l) {
    int r = -1;
    for (int i = l; i <= n; ++i) {
      if (peak[i] - peak[l] + 1 == length) {
        r = i;
      }
    }

    if (r == -1) {
      continue;
    }

    map<long long, vector<array<mint, 2>>> ways;
    ways[peak[l] - 1] = {{0, 1}};
    ways[peak[l] + 1] = {};

    for (int i = l; i < r; ++i) {
      if (peak[i + 1] == peak[i]) {
        continue;
      }

      map<long long, vector<array<mint, 2>>> new_ways = ways;
      if (peak[i + 1] > peak[i]) {
        new_ways[peak[i] + 1] = (--ways.upper_bound(peak[i] + 1))->second;
        new_ways[peak[i + 1] + 1] = (--ways.upper_bound(peak[i + 1] + 1))->second;

        for (auto it = ++new_ways.begin(); it != new_ways.end(); ++it) {
          auto &[x, f] = *it;
          if (x > peak[i] && x <= peak[i + 1]) {
            auto prv = it, nxt = it;
            --prv, ++nxt;

            vector<array<mint, 2>> g;
            mint prefix = evaluate(prv->second, x - 1);
            for (long long y = x; y < min(x + N, nxt->first); ++y) {
              prefix += evaluate(f, y);
              g.push_back({y, prefix});
            }
            f = g;
          }
        }
      } else {
        new_ways[peak[i]] = (--ways.upper_bound(peak[i]))->second;
        new_ways[peak[i + 1]] = (--ways.upper_bound(peak[i + 1]))->second;

        for (auto &[x, f] : ways) {
          if (x >= peak[i + 1] && x < peak[i]) {
            if (new_ways.count(x + 1) == 0) {
              new_ways[x + 1] = f;
            }
          }
        }

        for (auto it = ++new_ways.begin(); it != new_ways.end(); ++it) {
          auto &[x, f] = *it;
          if (x >= peak[i + 1] && x < peak[i]) {
            auto prv = it, nxt = it;
            --prv, ++nxt;

            vector<array<mint, 2>> g;
            mint value = evaluate((--ways.lower_bound(x))->second, x - 1);
            for (long long y = x; y < min(x + N, nxt->first); ++y) {
              mint new_value = evaluate(f, y);
              g.push_back({y, value + new_value});
              value = new_value;
            }
            f = g;
          }
        }
      }
      swap(ways, new_ways);
    }

    ans += evaluate((--ways.upper_bound(peak[r]))->second, peak[r]);

    l = r;
  }

  cout << length << " " << ans << "\n";
}

```