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 <stdio.h>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const long long mod = 998244353;
typedef long long ll;

class MatrixG {  // 用来快速递推转移的矩阵，压缩存储
private:
  vector<ll> matrix;

  ll inline get_element(const vector<ll>& m, int i, int j) {
    if(i % 2 == 0) {
      return m[j-i];
    } else if (j - i - 1 >=0) {
      return m[j-i-1];
    } else {
      return 0;
    }
  }

  vector<ll> bin_pow(int len, ll deg) {
    if (1 == deg) {
      return vector<ll>(len, 1);
    }
    vector<ll> half_deg_ans = bin_pow(len, deg / 2);
    vector<ll> ans(len);

    for (int j = 0; j < len; ++j) {  // 由deg/2得到deg
      for (int i = 0; i <= j; ++i) {
        ans[j] = (ans[j] + get_element(half_deg_ans, 0, i) * get_element(half_deg_ans, i, j)) % mod;
      }
    }
    // TODO: deg&1
    if (deg & 1) {
      vector<ll> ans_true(len);
      for (int j = 0; j < len; ++j) {
        for (int i = 0; i <= j; ++i) {
          ans_true[j] = (ans_true[j] +(i != j || j%2 == 0 ? ans[i] : 0)) % mod;
        }
      }
      return ans_true;
    }
    return ans;
  }
public:
  MatrixG(int len, ll deg)  {
    matrix = bin_pow(len ,deg);
  }
  ll get(int i, int j) {
    return get_element(matrix, i, j);
  }
};

class Solution {
protected:
  bool inline sign(const ll& a) {
    return a >= 0;
  }

  void preprocess(const vector<ll>& a, vector<ll>& peaks) {
    // 输入序列的预处理
    // 首先把相邻递增或相邻递减区间合并
    // 然后求前缀得到峰值序列，首元素为0
    vector<ll> a_merged;
    int n = 0; // a_merged.size()
    for (auto& x : a) {
      if (0 == x) continue;
      if(n != 0 && sign(x) == sign(a_merged[n-1])) {  // 新加入的元素与前一项符号相同，则可合并
        a_merged[n-1] += x;
      } else {
        a_merged.push_back(x);
        ++n;
      }
    }

    peaks.push_back(0);
    for (auto& x : a_merged) {
      peaks.push_back(x + peaks.back());
    }
    ++n; // n = peaks.size()
  }

  ll get_max_len(const vector<ll>& peaks) {  // 求最长递增子序列长度
    if(peaks.empty()) {
      return 0;
    }
    ll max_len = 1;
    ll in = -peaks[0];
    for (auto& x : peaks) {
      in = max(in, -x);
      max_len = max(max_len, in + x + 1);
    }
    return max_len;
  }

  void conditional_dp(  // dp由cur-1转移到cur
      vector<ll>& dp,
      const vector<ll>& L,
      const vector<ll>& R,
      const vector<bool>& flipped,
      ll cur) {
    int n = dp.size();
    vector<ll> dp2(n);
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < j + !flipped[j]; ++i) {
        if (L[i] <= cur - 1 && cur - 1 <= R[i] &&
          L[j] <= cur && cur <= R[j]) {
          dp2[j] = (dp2[j] + dp[i]) % mod;
        }
      }
    }
    dp = dp2;
  }

  ll solve_group(const vector<ll>& peaks) {  // 求一组内的最长递增子序列
    vector<ll> sorted_peaks = peaks;
    sort(sorted_peaks.begin(), sorted_peaks.end());
    int n = peaks.size() - 1;  // 波峰所划分的区间个数
    vector<ll> L(n);
    vector<ll> R(n);
    vector<bool> flipped(n, false);
    for (int i = 0; i < n; ++i) {
      L[i] = peaks[i];
      R[i] = peaks[i + 1];
      if (0 != i) {  // 区间会在交点处重叠，需要去重
        if (L[i] < R[i]) {
          ++L[i];
        } else {
          --L[i];
        }
      }
      if (L[i] > R[i]) {
        swap(L[i], R[i]);
        flipped[i] = true;
      }
    }
    ll start = sorted_peaks[0], end = sorted_peaks.back();  // 所求序列为[start, end]
    vector<ll> dp(n);  // dp[i]表示截止到当前，i处前缀所具有的某一长度方案数。这一长度随着时间递增达到最长
    for (int i = 0; i < n; ++i) {  // 登记长度为1的方案数
      if (L[i] <= start && start <= R[i]) {
        dp[i] = 1;
      }
    }
    ll last = start;  // 最大值小于等于last序列的方案数已经计算完成了
    for (auto peak : sorted_peaks) {
      // TODO: 尝试把cur改为peak - 1
      ll cur = peak - 2; // 当前最值应该提升到cur
      if (last < cur) {
        ll dist = cur - last;  // 还差提升多少次
        vector<bool> is_active(n);
        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < i + !flipped[i]; ++j) {
            if (L[i] <= cur && cur <= R[i] && L[j] <= cur && cur <= R[j]) {
              // dp[i]可以由dp[j]推导得到更长的序列，特别注意的是，递增序列可以由自己推导出更长的序列
              is_active[i] = is_active[j] = true;
            }
          }
        }
        int count_interval = 0;
        vector<int> interval_map(n);  // 对活跃区间重新编号，将原区间编号映射到活跃区间编号上
        for (int i = 0; i < n; ++i) {
          if(is_active[i]) {
            interval_map[i] = count_interval++;
          }
        }
        MatrixG m(count_interval, dist);
        vector<ll> dp2(n);  // dp状态转移后得到dp2
        for (int j = 0; j < n; ++j) {
          for (int i = 0; i <= j; ++i) {
            // TODO: act才更新
            dp2[j] = (dp2[j] + dp[i] * m.get(interval_map[i], interval_map[j])) % mod;
          }
        }
        dp = dp2;
        last = cur;
      }
      for (cur = peak - 1; cur <= peak; ++cur) {
        if (last < cur) {
          conditional_dp(dp, L, R, flipped, cur);
          last = cur;
        }
      }
      cur = peak + 1;
      if (cur <= end && last < cur) {
        conditional_dp(dp, L, R, flipped, cur);
        last = cur;
      }
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
      // TODO: 尝试去掉这个判断
      if (L[i] <= end && end <= R[i]) {
        ans = (ans + dp[i]) % mod;
      }
    }
    return ans;
  }

public:
  vector<ll> solve(vector<ll>& a) {
    vector<ll> peaks;
    preprocess(a, peaks);
    int n = peaks.size();
    ll max_len = get_max_len(peaks);
    if (1 == max_len) {  // 序列递减
      ll num = 1;
      for (auto& x : a) {
        num = (num + abs(x)) % mod;
      }
      return {1, num};
    }
    int i = 0;
    ll num = 0;
    while (i < n) {  // 将子序列分组进行检测，同组的具有相同的（最小，最大）值
      int id = -1;
      for (int j = i + 1; j < n; ++j) {
        if(peaks[j] - peaks[i] + 1 == max_len) {  // 所有满足条件的j都要纳入分组，而不只是第一个，否则复杂度暴涨
          id = j;
        }
      }
      if (-1 == id) {  // 以peaks[i]开头没有合适分组，尝试下一个
        ++i;
        continue;
      }
      vector<ll> p_group(id - i + 1);
      for (int k = i; k <= id; ++k) {
        p_group[k-i] = peaks[k];
      }
      i = id + 1;
      num = (num + solve_group(p_group)) % mod;
    }
    return {max_len, num};
  }
};

int main() {
//  freopen("in.txt", "r", stdin);
  int n;
  scanf("%d", &n);
  ll x;
  scanf("%lld", &x); // no use
  vector<ll> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", &a[i]);
  }
  Solution sln;
  vector<ll> ans = sln.solve(a);
  printf("%lld %lld\n", ans[0], ans[1]);
  return 0;
}