#include <bits/stdc++.h>
#ifdef ALGO
#include "el_psy_congroo.hpp"
#else
#define DUMP(...) 1145141919810
#define CHECK(...) (__VA_ARGS__)
#endif

template<int MOD>
struct Integral {
  int v_ = 0;

  template<typename T> Integral(T v) : v_(norm(v)) {  // Implicit conversion is allowed.
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;

  template<typename T> T norm(T v) const {
    if constexpr(std::is_same<long long, T>::value) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }

  int val() const { return v_; }
  Integral& operator += (const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator -= (const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator *= (const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
  Integral& operator /= (const Integral& rhs) { v_ = v_ * 1LL * power(rhs.val(), MOD - 2) % MOD; return *this; }
  Integral operator + (const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
  Integral operator - (const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
  Integral operator * (const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
  Integral operator / (const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
  bool operator == (const Integral& rhs) const { return val() == rhs.val(); }
  bool operator != (const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator - () const { return Integral(-val()); }
  const Integral& operator ++ () { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator ++ (int) { Integral ret = *this; ++(*this); return ret; }
  const Integral& operator -- () { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator -- (int) { Integral ret = *this; --(*this); return ret; }

  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD; return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};

template<int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Int<>{") + std::to_string(v.val()) + "}";
}

template<int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;

  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;

  template<typename T>
  Integral<MOD> operator () (T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr(!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};

template<int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i) this->at(i) = this->at(i - 1) * this->at(1);
  }
};

const int MOD = 998244353;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;

// Binom binom(0);
// PowerTable<MOD> pw2(200000, 2);

using Vector = std::vector<Mint>;
using Matrix = std::vector<Vector>;

Matrix mul(const Matrix& lhs, const Matrix& rhs) {
  CHECK(lhs.size() > 0 && lhs[0].size() == rhs.size());
  Matrix ret(lhs.size(), Vector(rhs[0].size()));
  for (int i = 0; i < lhs.size(); ++i)
    for (int j = 0; j < lhs[0].size(); ++j)
      for (int k = 0; k < rhs[0].size(); ++k)
        ret[i][k] += lhs[i][j] * rhs[j][k];
  return ret;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;

  int n;
  reader >> n;
  using LL = long long;
  std::vector<LL> d(n + 1), s(n + 1);
  reader >> s[0];
  d[0] = -1;
  int m = 0;
  for (int i = 1; i <= n; ++i) {
    int x;
    reader >> x;
    if (x != 0) {
      ++m;
      d[m] = x;
      s[m] = s[m - 1] + d[m];
    }
  }
  n = m;
  d.resize(n + 1);
  s.resize(n + 1);
  LL longest = 1;
  LL vmin = s[0];
  for (int p = 1; p <= n; ++p) {
    vmin = std::min(vmin, s[p]);
    if (d[p] > 0 && s[p] > vmin) {
      longest = std::max(longest, s[p] - vmin + 1);
    }
  }
  Mint result = 0;
  if (longest == 1) {
    result = 1;
    for (int i = 1; i <= n; ++i)
      result += std::abs(d[i]);
    printf("%lld %d\n", longest, result.val());
    return 0;
  }
  std::vector<LL> events;
  auto append = [&](LL x) {
    events.emplace_back(x);
  };
  for (int i = 0; i <= n; ++i) {
    append(s[i]);
    append(s[i] + 1);
    append(s[i] - 1);
    append(s[i] - d[i]);
    append(s[i] - d[i] + 1);
    append(s[i] - d[i] - 1);
  }
  auto inside = [](LL a, LL s, LL d) {
    if (d >= 0) return s - d < a && a <= s;
    return s - d > a && a >= s;
  };
  std::sort(events.begin(), events.end());
  events.erase(std::unique(events.begin(), events.end()), events.end());
  std::vector<Matrix> matrices;
  for (int at = 0; at + 1 < events.size(); ++at) {
    LL l = events[at];
    LL r = events[at + 1];
    Matrix A(n + 1, Vector(n + 1));
    for (int i = 0; i <= n; ++i) {
      if (inside(r, s[i], d[i])) {
        for (int j = 0; j < i; ++j) {
          if (inside(l, s[j], d[j])) {
            A[i][j] = 1;
          }
        }
        if (d[i] > 0 && inside(l, s[i], d[i])) A[i][i] = 1;
      }
    }
    Matrix B(n + 1, Vector(n + 1));
    for (int i = 0; i <= n; ++i) B[i][i] = 1;
    LL t = r - l;
    while (t) {
      if (t & 1) B = mul(A, B);
      A = mul(A, A);
      t >>= 1;
    }
    matrices.emplace_back(std::move(B));
  }
  Matrix B(n + 1, Vector(1));
  for (int i = 0; i <= n; ++i) {
    if (inside(vmin, s[i], d[i])) {
      B[i][0] = 1;
    }
  }
  vmin = s[0];
  for (int p = 1; p <= n; ++p) {
    vmin = std::min(vmin, s[p]);
    bool ok = d[p] > 0 && s[p] > vmin && s[p] - vmin + 1 == longest;
    if (!ok) continue;
    LL vmax = s[p];
    Matrix B(n + 1, Vector(1));

    auto inside = [](LL a, LL s, LL d) {
      if (d >= 0) return s - d < a && a <= s;
      return s - d > a && a >= s;
    };
    for (int i = 0; i <= n; ++i) {
      if (inside(vmin, s[i], d[i])) {
        B[i][0] = 1;
      }
    }
    for (int at = 0; at + 1 < events.size(); ++at) {
      LL l = events[at];
      LL r = events[at + 1];
      if (!(vmin <= l && r <= vmax)) continue;
      B = mul(matrices[at], B);
    }
    result += B[p][0];
  }
  printf("%lld %d\n", longest, result.val());
}


### Prompt

Please formulate a cpp solution 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>
#ifdef ALGO
#include "el_psy_congroo.hpp"
#else
#define DUMP(...) 1145141919810
#define CHECK(...) (__VA_ARGS__)
#endif

template<int MOD>
struct Integral {
  int v_ = 0;

  template<typename T> Integral(T v) : v_(norm(v)) {  // Implicit conversion is allowed.
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;

  template<typename T> T norm(T v) const {
    if constexpr(std::is_same<long long, T>::value) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }

  int val() const { return v_; }
  Integral& operator += (const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator -= (const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator *= (const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
  Integral& operator /= (const Integral& rhs) { v_ = v_ * 1LL * power(rhs.val(), MOD - 2) % MOD; return *this; }
  Integral operator + (const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
  Integral operator - (const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
  Integral operator * (const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
  Integral operator / (const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
  bool operator == (const Integral& rhs) const { return val() == rhs.val(); }
  bool operator != (const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator - () const { return Integral(-val()); }
  const Integral& operator ++ () { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator ++ (int) { Integral ret = *this; ++(*this); return ret; }
  const Integral& operator -- () { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator -- (int) { Integral ret = *this; --(*this); return ret; }

  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD; return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};

template<int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Int<>{") + std::to_string(v.val()) + "}";
}

template<int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;

  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;

  template<typename T>
  Integral<MOD> operator () (T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr(!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};

template<int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i) this->at(i) = this->at(i - 1) * this->at(1);
  }
};

const int MOD = 998244353;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;

// Binom binom(0);
// PowerTable<MOD> pw2(200000, 2);

using Vector = std::vector<Mint>;
using Matrix = std::vector<Vector>;

Matrix mul(const Matrix& lhs, const Matrix& rhs) {
  CHECK(lhs.size() > 0 && lhs[0].size() == rhs.size());
  Matrix ret(lhs.size(), Vector(rhs[0].size()));
  for (int i = 0; i < lhs.size(); ++i)
    for (int j = 0; j < lhs[0].size(); ++j)
      for (int k = 0; k < rhs[0].size(); ++k)
        ret[i][k] += lhs[i][j] * rhs[j][k];
  return ret;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;

  int n;
  reader >> n;
  using LL = long long;
  std::vector<LL> d(n + 1), s(n + 1);
  reader >> s[0];
  d[0] = -1;
  int m = 0;
  for (int i = 1; i <= n; ++i) {
    int x;
    reader >> x;
    if (x != 0) {
      ++m;
      d[m] = x;
      s[m] = s[m - 1] + d[m];
    }
  }
  n = m;
  d.resize(n + 1);
  s.resize(n + 1);
  LL longest = 1;
  LL vmin = s[0];
  for (int p = 1; p <= n; ++p) {
    vmin = std::min(vmin, s[p]);
    if (d[p] > 0 && s[p] > vmin) {
      longest = std::max(longest, s[p] - vmin + 1);
    }
  }
  Mint result = 0;
  if (longest == 1) {
    result = 1;
    for (int i = 1; i <= n; ++i)
      result += std::abs(d[i]);
    printf("%lld %d\n", longest, result.val());
    return 0;
  }
  std::vector<LL> events;
  auto append = [&](LL x) {
    events.emplace_back(x);
  };
  for (int i = 0; i <= n; ++i) {
    append(s[i]);
    append(s[i] + 1);
    append(s[i] - 1);
    append(s[i] - d[i]);
    append(s[i] - d[i] + 1);
    append(s[i] - d[i] - 1);
  }
  auto inside = [](LL a, LL s, LL d) {
    if (d >= 0) return s - d < a && a <= s;
    return s - d > a && a >= s;
  };
  std::sort(events.begin(), events.end());
  events.erase(std::unique(events.begin(), events.end()), events.end());
  std::vector<Matrix> matrices;
  for (int at = 0; at + 1 < events.size(); ++at) {
    LL l = events[at];
    LL r = events[at + 1];
    Matrix A(n + 1, Vector(n + 1));
    for (int i = 0; i <= n; ++i) {
      if (inside(r, s[i], d[i])) {
        for (int j = 0; j < i; ++j) {
          if (inside(l, s[j], d[j])) {
            A[i][j] = 1;
          }
        }
        if (d[i] > 0 && inside(l, s[i], d[i])) A[i][i] = 1;
      }
    }
    Matrix B(n + 1, Vector(n + 1));
    for (int i = 0; i <= n; ++i) B[i][i] = 1;
    LL t = r - l;
    while (t) {
      if (t & 1) B = mul(A, B);
      A = mul(A, A);
      t >>= 1;
    }
    matrices.emplace_back(std::move(B));
  }
  Matrix B(n + 1, Vector(1));
  for (int i = 0; i <= n; ++i) {
    if (inside(vmin, s[i], d[i])) {
      B[i][0] = 1;
    }
  }
  vmin = s[0];
  for (int p = 1; p <= n; ++p) {
    vmin = std::min(vmin, s[p]);
    bool ok = d[p] > 0 && s[p] > vmin && s[p] - vmin + 1 == longest;
    if (!ok) continue;
    LL vmax = s[p];
    Matrix B(n + 1, Vector(1));

    auto inside = [](LL a, LL s, LL d) {
      if (d >= 0) return s - d < a && a <= s;
      return s - d > a && a >= s;
    };
    for (int i = 0; i <= n; ++i) {
      if (inside(vmin, s[i], d[i])) {
        B[i][0] = 1;
      }
    }
    for (int at = 0; at + 1 < events.size(); ++at) {
      LL l = events[at];
      LL r = events[at + 1];
      if (!(vmin <= l && r <= vmax)) continue;
      B = mul(matrices[at], B);
    }
    result += B[p][0];
  }
  printf("%lld %d\n", longest, result.val());
}


```