#include <bits/stdc++.h>

const int MOD = 998244353;

void add(int &x, int a) {
  x += a;
  if (x >= MOD) {
    x -= MOD;
  }
}

int inverse(int a) {
  return a == 1 ? 1 : 1LL * (MOD - MOD / a) * inverse(MOD % a) % MOD;
}

const int N = 50;

int binom[N + 1][N + 1], ifact[N + 1];

int sub_count(long long lis, const long long *steps, const long long *y,
              int n) {
  //   printf("n=%d\n", n);
  static int dp[N], cross_ways[N + 1];
  // y[0] (steps[0]) y[1] ... (steps[n - 1]) y[n]
  if (n <= 0) {
    return 0;
  }
  std::vector<long long> yvalues;
  for (int i = 0; i <= n; ++i) {
    yvalues.push_back(y[i]);
  }
  std::sort(yvalues.begin(), yvalues.end());
  yvalues.erase(std::unique(yvalues.begin(), yvalues.end()), yvalues.end());
  if (yvalues.back() - yvalues.front() + 1 != lis) {
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    dp[i] = y[i] == yvalues[0];
  }
  // n <= 50
  // n segments
  // (n + 1) points
  for (int yindex = 1; yindex < static_cast<int>(yvalues.size()); ++yindex) {
    long long ydelta = yvalues[yindex] - yvalues[yindex - 1] - 1;
    for (int crosses = 1; crosses <= n; crosses += 2) {
      cross_ways[crosses] = 0;
    }
    for (int d = 0; d <= (n >> 1) && d <= ydelta; ++d) {
      int y0 = (ydelta + MOD - d) % MOD;
      int numerator = 1;
      for (int crosses = 1; crosses <= n; crosses += 2) {
        int ups = (crosses + 1) >> 1;
        int downs = crosses >> 1;
        if (d <= downs) {
          add(cross_ways[crosses],
              1LL * numerator * ifact[ups - 1] % MOD * binom[downs][d] % MOD);
        }
        numerator = 1LL * numerator * (y0 + ups) % MOD;
      }
    }
    // printf("y=%lld\n", yvalues[yindex]);
    for (int j = n; j--;) {
      bool contained_j;
      if (steps[j] > 0) {
        contained_j = y[j] <= yvalues[yindex] && yvalues[yindex] <= y[j + 1];
      } else {
        contained_j = y[j] > yvalues[yindex] && yvalues[yindex] > y[j + 1];
      }
      //   printf("\tj=%d contained=%d\n", j, contained_j);
      if (contained_j) {
        int crosses = 0;
        int result = 0;
        for (int i = j; i >= 0; --i) {
          if (steps[i] > 0) {
            crosses += 2 * y[i] < 2 * yvalues[yindex] - 1 &&
                       2 * yvalues[yindex] - 1 < 2 * y[i + 1];
            // if (dp[i]) {
            //   printf("\t\t%d->%d crosses=%d\n", i, j, crosses);
            // }
            add(result, 1LL * dp[i] * cross_ways[crosses] % MOD);
          } else {
            // if (dp[i]) {
            //   printf("\t\t%d->%d crosses=%d\n", i, j, crosses);
            // }
            add(result, 1LL * dp[i] * cross_ways[crosses] % MOD);
            if (i < j) {
              crosses += 2 * y[i] > 2 * yvalues[yindex] - 1 &&
                         2 * yvalues[yindex] - 1 > 2 * y[i + 1];
            }
          }
        }
        dp[j] = result;
      } else {
        dp[j] = 0;
      }
    }
  }
  int result = 0;
  for (int i = 0; i < n; ++i) {
    add(result, dp[i]);
  }
  return result;
}

int main() {
  for (int i = 0; i <= N; ++i) {
    binom[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
    }
  }
  ifact[0] = 1;
  for (int i = 1; i <= N; ++i) {
    ifact[i] = 1LL * ifact[i - 1] * inverse(i) % MOD;
  }
  static long long steps[N], y[N + 2];
  int n0;
  while (scanf("%d%*d", &n0) == 1) {
    int n = 0;
    while (n0--) {
      int x;
      scanf("%d", &x);
      if (x != 0) {
        if (n && (steps[n - 1] >= 0) == (x >= 0)) {
          steps[n - 1] += x;
        } else {
          steps[n++] = x;
        }
      }
    }
    y[0] = 0;
    for (int i = 0; i < n; ++i) {
      y[i + 1] = y[i] + steps[i];
    }
    long long lis = 1;
    {
      long long min_y = 0;
      for (int i = 1; i <= n; ++i) {
        lis = std::max(lis, y[i] - min_y + 1);
        min_y = std::min(min_y, y[i]);
      }
    }
    if (lis == 1) {
      int ways = 1;
      for (int i = 0; i < n; ++i) {
        add(ways, std::abs(steps[i]) % MOD);
      }
      printf("1 %d\n", ways);
      continue;
    }
    int result = 0;
    for (int i0 = 0, i = 1; i <= n + 1; ++i) {
      if (i == n + 1 || y[i] < y[i0]) {
        add(result, sub_count(lis, steps + i0, y + i0, i - i0 - 1));
        i0 = i;
      }
    }
    printf("%lld %d\n", lis, result);
  }
}
### Prompt

Construct a cpp code solution to the problem outlined:

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 int MOD = 998244353;

void add(int &x, int a) {
  x += a;
  if (x >= MOD) {
    x -= MOD;
  }
}

int inverse(int a) {
  return a == 1 ? 1 : 1LL * (MOD - MOD / a) * inverse(MOD % a) % MOD;
}

const int N = 50;

int binom[N + 1][N + 1], ifact[N + 1];

int sub_count(long long lis, const long long *steps, const long long *y,
              int n) {
  //   printf("n=%d\n", n);
  static int dp[N], cross_ways[N + 1];
  // y[0] (steps[0]) y[1] ... (steps[n - 1]) y[n]
  if (n <= 0) {
    return 0;
  }
  std::vector<long long> yvalues;
  for (int i = 0; i <= n; ++i) {
    yvalues.push_back(y[i]);
  }
  std::sort(yvalues.begin(), yvalues.end());
  yvalues.erase(std::unique(yvalues.begin(), yvalues.end()), yvalues.end());
  if (yvalues.back() - yvalues.front() + 1 != lis) {
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    dp[i] = y[i] == yvalues[0];
  }
  // n <= 50
  // n segments
  // (n + 1) points
  for (int yindex = 1; yindex < static_cast<int>(yvalues.size()); ++yindex) {
    long long ydelta = yvalues[yindex] - yvalues[yindex - 1] - 1;
    for (int crosses = 1; crosses <= n; crosses += 2) {
      cross_ways[crosses] = 0;
    }
    for (int d = 0; d <= (n >> 1) && d <= ydelta; ++d) {
      int y0 = (ydelta + MOD - d) % MOD;
      int numerator = 1;
      for (int crosses = 1; crosses <= n; crosses += 2) {
        int ups = (crosses + 1) >> 1;
        int downs = crosses >> 1;
        if (d <= downs) {
          add(cross_ways[crosses],
              1LL * numerator * ifact[ups - 1] % MOD * binom[downs][d] % MOD);
        }
        numerator = 1LL * numerator * (y0 + ups) % MOD;
      }
    }
    // printf("y=%lld\n", yvalues[yindex]);
    for (int j = n; j--;) {
      bool contained_j;
      if (steps[j] > 0) {
        contained_j = y[j] <= yvalues[yindex] && yvalues[yindex] <= y[j + 1];
      } else {
        contained_j = y[j] > yvalues[yindex] && yvalues[yindex] > y[j + 1];
      }
      //   printf("\tj=%d contained=%d\n", j, contained_j);
      if (contained_j) {
        int crosses = 0;
        int result = 0;
        for (int i = j; i >= 0; --i) {
          if (steps[i] > 0) {
            crosses += 2 * y[i] < 2 * yvalues[yindex] - 1 &&
                       2 * yvalues[yindex] - 1 < 2 * y[i + 1];
            // if (dp[i]) {
            //   printf("\t\t%d->%d crosses=%d\n", i, j, crosses);
            // }
            add(result, 1LL * dp[i] * cross_ways[crosses] % MOD);
          } else {
            // if (dp[i]) {
            //   printf("\t\t%d->%d crosses=%d\n", i, j, crosses);
            // }
            add(result, 1LL * dp[i] * cross_ways[crosses] % MOD);
            if (i < j) {
              crosses += 2 * y[i] > 2 * yvalues[yindex] - 1 &&
                         2 * yvalues[yindex] - 1 > 2 * y[i + 1];
            }
          }
        }
        dp[j] = result;
      } else {
        dp[j] = 0;
      }
    }
  }
  int result = 0;
  for (int i = 0; i < n; ++i) {
    add(result, dp[i]);
  }
  return result;
}

int main() {
  for (int i = 0; i <= N; ++i) {
    binom[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
    }
  }
  ifact[0] = 1;
  for (int i = 1; i <= N; ++i) {
    ifact[i] = 1LL * ifact[i - 1] * inverse(i) % MOD;
  }
  static long long steps[N], y[N + 2];
  int n0;
  while (scanf("%d%*d", &n0) == 1) {
    int n = 0;
    while (n0--) {
      int x;
      scanf("%d", &x);
      if (x != 0) {
        if (n && (steps[n - 1] >= 0) == (x >= 0)) {
          steps[n - 1] += x;
        } else {
          steps[n++] = x;
        }
      }
    }
    y[0] = 0;
    for (int i = 0; i < n; ++i) {
      y[i + 1] = y[i] + steps[i];
    }
    long long lis = 1;
    {
      long long min_y = 0;
      for (int i = 1; i <= n; ++i) {
        lis = std::max(lis, y[i] - min_y + 1);
        min_y = std::min(min_y, y[i]);
      }
    }
    if (lis == 1) {
      int ways = 1;
      for (int i = 0; i < n; ++i) {
        add(ways, std::abs(steps[i]) % MOD);
      }
      printf("1 %d\n", ways);
      continue;
    }
    int result = 0;
    for (int i0 = 0, i = 1; i <= n + 1; ++i) {
      if (i == n + 1 || y[i] < y[i0]) {
        add(result, sub_count(lis, steps + i0, y + i0, i - i0 - 1));
        i0 = i;
      }
    }
    printf("%lld %d\n", lis, result);
  }
}
```