# include <algorithm>
# include <iostream>
# include <vector>

using namespace std;

using ll = long long;
constexpr int P = 998244353;

int power(int a, int b) {
  int res = 1;
  for (; b > 0; b /= 2, a = ll(a) * a % P) {
    if (b % 2 == 1) {
      res = ll(res) * a % P;
    }
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<ll> 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);
    }
  }
  ll ans = 0;
  n = x.size();
  vector<int> fac(n + 1), invfac(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = ll(fac[i - 1]) * i % P;
  }
  for (int i = 0; i <= n; i++) {
    invfac[i] = power(fac[i], P - 2);
  }
  vector<ll> 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);
    }
    ans = max(ans, len[i]);
  }
  if (ans == 1) {
    cout << "1 " << (x[0] - x[n - 1] + 1) % P << "\n";
    return 0;
  }
  auto solve = [&](vector<ll> x) {
    int n = x.size();
    vector<bool> type(n);
    vector<tuple<ll, int, bool>> events;
    events.emplace_back(x[0], 0, true);
    events.emplace_back(x[0] + 1, 0, false);
    for (int i = 1; i < n; i++) {
      if (x[i - 1] < x[i]) {
        type[i] = true;
        events.emplace_back(x[i - 1] + 1, i, true);
        events.emplace_back(x[i] + 1, i, false);
      } else {
        events.emplace_back(x[i], i, true);
        events.emplace_back(x[i - 1], i, false);
      }
    }
    sort(events.begin(), events.end());
    ll last = x[0] + 1;
    vector<bool> able(n);
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
      if (x[i] == x[0]) {
        dp[i] = 1;
      }
    }
    for (auto [v, i, t] : events) {
      v = min(max(x[0] + 1, v), x[0] + ans);
      ll times = v - last;
      if (times == 0) {
        able[i] = t;
        continue;
      }
      times--;
      vector<vector<int>> f(n + 1, vector<int>(n + 1));
      for (int i = 0; i <= n; i++) {
        f[i][0] = 1;
        for (int j = 1; j <= n; j++) {
          f[i][j] = ll(f[i][j - 1]) * (times % P - i + j + P) % P;
        }
      }
      for (int i = n - 1; i >= 0; i--) {
        if (!able[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 (able[k]) {
              if (type[k]) {
                b++;
              } else {
                a++;
                if (k == i) {
                  a--;
                }
                if (k == j) {
                  a--;
                }
              }
            }
          }
          int coef = 0;
          for (int k = 0; k <= a && k <= times; k++) {
            coef = (coef + ll(fac[a]) * invfac[k] % P * invfac[a - k] % P * (b == 0 ? ll(k == times) : ll(f[k][b - 1]) * invfac[b - 1] % P)) % P;
          }
          newdp = (newdp + ll(dp[j]) * coef) % P;
        }
        dp[i] = newdp;
      }
      last = v;
      able[i] = t;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = (res + dp[i]) % P;
    }
    return res;
  };
  int ways = 0;
  int last = -1;
  ll val = 1e18;
  for (int i = 0; i < n; i++) {
    if (len[i] == ans && x[i] < val) {
      if (last != -1) {
        ways = (ways + solve(vector<ll>(x.begin() + last, x.begin() + i))) % P;
      }
      last = i;
      val = x[i];
    }
  }
  ways = (ways + solve(vector<ll>(x.begin() + last, x.begin() + n))) % P;
  cout << ans << " " << ways << "\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 <algorithm>
# include <iostream>
# include <vector>

using namespace std;

using ll = long long;
constexpr int P = 998244353;

int power(int a, int b) {
  int res = 1;
  for (; b > 0; b /= 2, a = ll(a) * a % P) {
    if (b % 2 == 1) {
      res = ll(res) * a % P;
    }
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<ll> 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);
    }
  }
  ll ans = 0;
  n = x.size();
  vector<int> fac(n + 1), invfac(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = ll(fac[i - 1]) * i % P;
  }
  for (int i = 0; i <= n; i++) {
    invfac[i] = power(fac[i], P - 2);
  }
  vector<ll> 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);
    }
    ans = max(ans, len[i]);
  }
  if (ans == 1) {
    cout << "1 " << (x[0] - x[n - 1] + 1) % P << "\n";
    return 0;
  }
  auto solve = [&](vector<ll> x) {
    int n = x.size();
    vector<bool> type(n);
    vector<tuple<ll, int, bool>> events;
    events.emplace_back(x[0], 0, true);
    events.emplace_back(x[0] + 1, 0, false);
    for (int i = 1; i < n; i++) {
      if (x[i - 1] < x[i]) {
        type[i] = true;
        events.emplace_back(x[i - 1] + 1, i, true);
        events.emplace_back(x[i] + 1, i, false);
      } else {
        events.emplace_back(x[i], i, true);
        events.emplace_back(x[i - 1], i, false);
      }
    }
    sort(events.begin(), events.end());
    ll last = x[0] + 1;
    vector<bool> able(n);
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
      if (x[i] == x[0]) {
        dp[i] = 1;
      }
    }
    for (auto [v, i, t] : events) {
      v = min(max(x[0] + 1, v), x[0] + ans);
      ll times = v - last;
      if (times == 0) {
        able[i] = t;
        continue;
      }
      times--;
      vector<vector<int>> f(n + 1, vector<int>(n + 1));
      for (int i = 0; i <= n; i++) {
        f[i][0] = 1;
        for (int j = 1; j <= n; j++) {
          f[i][j] = ll(f[i][j - 1]) * (times % P - i + j + P) % P;
        }
      }
      for (int i = n - 1; i >= 0; i--) {
        if (!able[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 (able[k]) {
              if (type[k]) {
                b++;
              } else {
                a++;
                if (k == i) {
                  a--;
                }
                if (k == j) {
                  a--;
                }
              }
            }
          }
          int coef = 0;
          for (int k = 0; k <= a && k <= times; k++) {
            coef = (coef + ll(fac[a]) * invfac[k] % P * invfac[a - k] % P * (b == 0 ? ll(k == times) : ll(f[k][b - 1]) * invfac[b - 1] % P)) % P;
          }
          newdp = (newdp + ll(dp[j]) * coef) % P;
        }
        dp[i] = newdp;
      }
      last = v;
      able[i] = t;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = (res + dp[i]) % P;
    }
    return res;
  };
  int ways = 0;
  int last = -1;
  ll val = 1e18;
  for (int i = 0; i < n; i++) {
    if (len[i] == ans && x[i] < val) {
      if (last != -1) {
        ways = (ways + solve(vector<ll>(x.begin() + last, x.begin() + i))) % P;
      }
      last = i;
      val = x[i];
    }
  }
  ways = (ways + solve(vector<ll>(x.begin() + last, x.begin() + n))) % P;
  cout << ans << " " << ways << "\n";
  return 0;
}
```