#include <bits/stdc++.h>

const long long MOD = 998244353;

using namespace std;

typedef long long ll;

vector<ll> binpow(int len, ll deg) {  // len*len的矩阵G^deg的压缩表示形式，返回矩阵第一行，O(n^2 log d)
  if (deg == 1) return vector<ll>(len, 1);
  vector<ll> part = binpow(len, deg / 2);
  vector<ll> whole(len);

  auto D = [&](int i, int j){  // 由压缩表示解码出矩阵元素(i,j)
    assert(i <= j);
    if (i % 2 == 0) return part[j - i];
    return j - i - 1 >= 0 ? part[j - i - 1] : 0;
  };

  for (int j = 0; j < len; j++) { // part合并为whole，从G^{deg/2}变为G^{deg}
    for (int i = 0; i <= j; i++) {
      whole[j] = (whole[j] + D(0, i) * D(i, j)) % MOD;
    }
  }

  if (deg % 2 == 1) {  // 乘G
    vector<ll> whole2(len);
    for (int j = 0; j < len; j++) {
      for (int i = 0; i <= j; i++) {
        whole2[j] = (whole2[j] + (i != j || j % 2 == 0 ? whole[i] : 0)) % MOD;
      }
    }
    return whole2;
  }
  return whole;
}

void simple_transition(vector<ll> &dp, vector<long long> &L, vector<long long> &R, vector<long long> &fl, long long z) {  // [z, z-1]的单步更新，O(n^2)，尝试优化到O(n log n) ?
  vector<ll> dp2(dp.size());
  for (int i = 0; i < dp.size(); i++) {
    for (int j = 0; j < i + (fl[i] == 1); j++) {
      if (L[i] <= z && z <= R[i] && L[j] <= z - 1 && z - 1 <= R[j]) {
        dp2[i] = (dp2[i] + dp[j]) % MOD;
      }
    }
  }
  dp = dp2;
}

long long solve(const vector<long long>& b) {  // O(n^2 log d)计算一个候选区间上的最长递增子序列数目
  vector<long long> c = b;
  sort(c.begin(), c.end());
  int sz = b.size() - 1;  // 小区间的个数
  // LR表示区间的左右端点，fl表示是否经过反转处理，经过反转处理后递减区间变为递增区间
  vector<long long> L(sz);
  vector<long long> R(sz);
  vector<long long> fl(sz, 1);
  for (int i = 0; i + 1 < b.size(); i++) {
    L[i] = b[i];
    R[i] = b[i + 1];

    if (i != 0) {
      if (L[i] < R[i]) L[i]++;
      else L[i]--;
    }

    if (L[i] > R[i]) swap(L[i], R[i]), fl[i] = -1;
  }
  vector<ll> dp(sz);
  long long fr = c[0], to = c.back(); // (from, to), 表示总区间的最小值和最大值
  for (int i = 0; i < sz; i++) {  // 最小值在单个区间内部时，单个区间的dp置1
    if (L[i] <= fr && fr <= R[i]) {
      dp[i] = 1;
    }
  }
  long long lst = fr; // last，表示最近处理的峰值
  for (auto p : c) {
    // 对于每个峰值，由小到大处理.
    // 对于每个子区间，求前缀中构成[from, p)的方案数
    long long z = p - 2;
    if (lst < z)  {
      // 上一个处理的峰值比p-2还要小
      // 将序列长度从lst一次性扩展到z = p - 2，保证这之间没有峰值
      // 即包含z的区间一定包含[lst,z]
      long long d = z - lst;
      vector<int> act(sz);
      for (int i = 0; i < sz; i++) {
        for (int j = 0; j < i + (fl[i] == 1); j++) {  // 每个区间要考虑自己之前的所有区间，递增区间还要考虑自己
          if (L[i] <= z && z <= R[i] && L[j] <= z && z <= R[j]) {  // 这一对区间都包含z=p-2，act置1，表示区间活跃？
            act[i] = 1;
            act[j] = 1;
          }
        }
      }
      int cnt = 0;
      vector<int> link(sz);
      for (int i = 0; i < sz; i++)
        if (act[i])
          link[i] = cnt++;
      vector<ll> fast = binpow(cnt, d);  // 一共cnt个区间活跃，需要把它们提升d度
      vector<ll> dp2(sz);
      auto D = [&](int i, int j){  // 矩阵G^d的解码，同binpow里
        if (i % 2 == 0) return fast[j - i];
        return (j - i - 1 >= 0 ? fast[j - i - 1] : 0);
      };
      for (int i = 0; i < sz; i++) {
        for (int j = 0; j <= i; j++) {
          dp2[i] = (dp2[i] + dp[j] * D(link[j], link[i])) % MOD;
        }
      }
      dp = dp2;
      lst = z;
    }

    z = p - 1;
    if (lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
    z = p;
    if (lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
    z = p + 1;
    if (z <= to && lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
  }
  long long res = 0;
  for (int i = 0; i < sz; i++) {
    if (L[i] <= to && to <= R[i]) {
      res = (res + dp[i]) % MOD;
    }
  }
  return res;
}

int inline sign(long long x) {
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;
}

int main() {
  int n;
  scanf("%d", &n);
  long long x;
  scanf("%lld", &x);  // 此时采用的x实际上无用
  vector<long long> a;
  for (int i = 0; i < n; i++) {  // O(n)的数组预处理
    scanf("%lld", &x);  // 此处x发生了转义，是题干里的d_i，在累加中可能溢出，所以是long long
    if (x != 0) {  // 区间合并技巧：两个连续递增或两个连续递减可以合并，最后呈现“增、减、增、减”的锯齿状
      if (a.size() && sign(a.back()) == sign(x)) {
        a[a.size() - 1] += x;
      } else {
        a.push_back(x);
      }
    }
  }
  vector<long long> peaks;
  peaks.push_back(1);
  n = a.size();
  for (int i = 0; i < n; i++) {  // 由题设的差分序列求出原值的峰值序列
    peaks.push_back(a[i] + peaks.back());
  }
  n++;  // n==peak.size()
  long long max_len = 1;
  for (int i = 0; i < n; i++) {  // O(n^2)计算最长递增子序列的长度，可以采用股票量化交易的方法优化至O(n)
    for (int j = i + 1; j < n; j++) {
      if (peaks[i] < peaks[j])
        max_len = max(max_len, peaks[j] - peaks[i] + 1);
    }
  }

  if (max_len == 1) {  // 1时特殊处理，等于总长度
    long long ans = 1;
    for (int i = 0; i < a.size(); i++) {
      ans = (ans + abs(a[i])) % MOD;
    }
    printf("1 %lld\n", ans);
    return 0;
  }

  printf("%lld ", max_len);
  long long ans = 0;
  int i = 0;
  while (i < n) {  // 筛选每个候选区间p'并送入solve计算结果, 外层递归n轮，内层复杂度O(n^2 log d)
    int id = -1;
    for (int j = i + 1; j < n; j++) {
      if (peaks[j] - peaks[i] + 1 == max_len) {
        id = j;
      }
    }
    if (id == -1) {
      i++;
      continue;
    }
    vector<long long> b;
    for (int k = i; k <= id; k++) {
      b.push_back(peaks[k]);
    }
    i = id;
    ans = (ans + solve(b)) % MOD;
  }
  printf("%lld\n", ans);
}
### 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>

const long long MOD = 998244353;

using namespace std;

typedef long long ll;

vector<ll> binpow(int len, ll deg) {  // len*len的矩阵G^deg的压缩表示形式，返回矩阵第一行，O(n^2 log d)
  if (deg == 1) return vector<ll>(len, 1);
  vector<ll> part = binpow(len, deg / 2);
  vector<ll> whole(len);

  auto D = [&](int i, int j){  // 由压缩表示解码出矩阵元素(i,j)
    assert(i <= j);
    if (i % 2 == 0) return part[j - i];
    return j - i - 1 >= 0 ? part[j - i - 1] : 0;
  };

  for (int j = 0; j < len; j++) { // part合并为whole，从G^{deg/2}变为G^{deg}
    for (int i = 0; i <= j; i++) {
      whole[j] = (whole[j] + D(0, i) * D(i, j)) % MOD;
    }
  }

  if (deg % 2 == 1) {  // 乘G
    vector<ll> whole2(len);
    for (int j = 0; j < len; j++) {
      for (int i = 0; i <= j; i++) {
        whole2[j] = (whole2[j] + (i != j || j % 2 == 0 ? whole[i] : 0)) % MOD;
      }
    }
    return whole2;
  }
  return whole;
}

void simple_transition(vector<ll> &dp, vector<long long> &L, vector<long long> &R, vector<long long> &fl, long long z) {  // [z, z-1]的单步更新，O(n^2)，尝试优化到O(n log n) ?
  vector<ll> dp2(dp.size());
  for (int i = 0; i < dp.size(); i++) {
    for (int j = 0; j < i + (fl[i] == 1); j++) {
      if (L[i] <= z && z <= R[i] && L[j] <= z - 1 && z - 1 <= R[j]) {
        dp2[i] = (dp2[i] + dp[j]) % MOD;
      }
    }
  }
  dp = dp2;
}

long long solve(const vector<long long>& b) {  // O(n^2 log d)计算一个候选区间上的最长递增子序列数目
  vector<long long> c = b;
  sort(c.begin(), c.end());
  int sz = b.size() - 1;  // 小区间的个数
  // LR表示区间的左右端点，fl表示是否经过反转处理，经过反转处理后递减区间变为递增区间
  vector<long long> L(sz);
  vector<long long> R(sz);
  vector<long long> fl(sz, 1);
  for (int i = 0; i + 1 < b.size(); i++) {
    L[i] = b[i];
    R[i] = b[i + 1];

    if (i != 0) {
      if (L[i] < R[i]) L[i]++;
      else L[i]--;
    }

    if (L[i] > R[i]) swap(L[i], R[i]), fl[i] = -1;
  }
  vector<ll> dp(sz);
  long long fr = c[0], to = c.back(); // (from, to), 表示总区间的最小值和最大值
  for (int i = 0; i < sz; i++) {  // 最小值在单个区间内部时，单个区间的dp置1
    if (L[i] <= fr && fr <= R[i]) {
      dp[i] = 1;
    }
  }
  long long lst = fr; // last，表示最近处理的峰值
  for (auto p : c) {
    // 对于每个峰值，由小到大处理.
    // 对于每个子区间，求前缀中构成[from, p)的方案数
    long long z = p - 2;
    if (lst < z)  {
      // 上一个处理的峰值比p-2还要小
      // 将序列长度从lst一次性扩展到z = p - 2，保证这之间没有峰值
      // 即包含z的区间一定包含[lst,z]
      long long d = z - lst;
      vector<int> act(sz);
      for (int i = 0; i < sz; i++) {
        for (int j = 0; j < i + (fl[i] == 1); j++) {  // 每个区间要考虑自己之前的所有区间，递增区间还要考虑自己
          if (L[i] <= z && z <= R[i] && L[j] <= z && z <= R[j]) {  // 这一对区间都包含z=p-2，act置1，表示区间活跃？
            act[i] = 1;
            act[j] = 1;
          }
        }
      }
      int cnt = 0;
      vector<int> link(sz);
      for (int i = 0; i < sz; i++)
        if (act[i])
          link[i] = cnt++;
      vector<ll> fast = binpow(cnt, d);  // 一共cnt个区间活跃，需要把它们提升d度
      vector<ll> dp2(sz);
      auto D = [&](int i, int j){  // 矩阵G^d的解码，同binpow里
        if (i % 2 == 0) return fast[j - i];
        return (j - i - 1 >= 0 ? fast[j - i - 1] : 0);
      };
      for (int i = 0; i < sz; i++) {
        for (int j = 0; j <= i; j++) {
          dp2[i] = (dp2[i] + dp[j] * D(link[j], link[i])) % MOD;
        }
      }
      dp = dp2;
      lst = z;
    }

    z = p - 1;
    if (lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
    z = p;
    if (lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
    z = p + 1;
    if (z <= to && lst < z) {
      simple_transition(dp, L, R, fl, z);
      lst = z;
    }
  }
  long long res = 0;
  for (int i = 0; i < sz; i++) {
    if (L[i] <= to && to <= R[i]) {
      res = (res + dp[i]) % MOD;
    }
  }
  return res;
}

int inline sign(long long x) {
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;
}

int main() {
  int n;
  scanf("%d", &n);
  long long x;
  scanf("%lld", &x);  // 此时采用的x实际上无用
  vector<long long> a;
  for (int i = 0; i < n; i++) {  // O(n)的数组预处理
    scanf("%lld", &x);  // 此处x发生了转义，是题干里的d_i，在累加中可能溢出，所以是long long
    if (x != 0) {  // 区间合并技巧：两个连续递增或两个连续递减可以合并，最后呈现“增、减、增、减”的锯齿状
      if (a.size() && sign(a.back()) == sign(x)) {
        a[a.size() - 1] += x;
      } else {
        a.push_back(x);
      }
    }
  }
  vector<long long> peaks;
  peaks.push_back(1);
  n = a.size();
  for (int i = 0; i < n; i++) {  // 由题设的差分序列求出原值的峰值序列
    peaks.push_back(a[i] + peaks.back());
  }
  n++;  // n==peak.size()
  long long max_len = 1;
  for (int i = 0; i < n; i++) {  // O(n^2)计算最长递增子序列的长度，可以采用股票量化交易的方法优化至O(n)
    for (int j = i + 1; j < n; j++) {
      if (peaks[i] < peaks[j])
        max_len = max(max_len, peaks[j] - peaks[i] + 1);
    }
  }

  if (max_len == 1) {  // 1时特殊处理，等于总长度
    long long ans = 1;
    for (int i = 0; i < a.size(); i++) {
      ans = (ans + abs(a[i])) % MOD;
    }
    printf("1 %lld\n", ans);
    return 0;
  }

  printf("%lld ", max_len);
  long long ans = 0;
  int i = 0;
  while (i < n) {  // 筛选每个候选区间p'并送入solve计算结果, 外层递归n轮，内层复杂度O(n^2 log d)
    int id = -1;
    for (int j = i + 1; j < n; j++) {
      if (peaks[j] - peaks[i] + 1 == max_len) {
        id = j;
      }
    }
    if (id == -1) {
      i++;
      continue;
    }
    vector<long long> b;
    for (int k = i; k <= id; k++) {
      b.push_back(peaks[k]);
    }
    i = id;
    ans = (ans + solve(b)) % MOD;
  }
  printf("%lld\n", ans);
}
```