1 2 3 4 ...

• 时间限制：5 秒

• 内存限制：256 MiB

题目描述

Igor 有一个整数序列 $d_1,d_2,\ldots,d_n$。当 Igor 进入教室时，黑板上写着一个整数 $x$。

Igor 按照如下过程生成序列 $p$：

1. 初始时，$p=[x]$；
2. 对于每个 $1\le i\le n$，执行 $|d_i|$ 次操作：
   • 若 $d_i\ge 0$，设当前 $p$ 的最后一个元素为 $y$，在 $p$ 末尾加入 $y+1$；
   • 若 $d_i<0$，设当前 $p$ 的最后一个元素为 $y$，在 $p$ 末尾加入 $y-1$。

例如，当 $x=3$ 且 $d=[1,-1,2]$ 时，生成的序列为 $p=[3,4,3,4,5]$。

请计算 $p$ 的最长严格递增子序列长度，以及这样的子序列个数。

如果序列 $a$ 可以通过从序列 $b$ 中删除若干元素得到，则称 $a$ 是 $b$ 的一个子序列。删除的元素个数可以为零，也可以等于 $b$ 的长度。

如果序列 $a$ 中每个元素（除第一个外）都严格大于前一个元素，则称 $a$ 是严格递增序列。

对于 $p=[3,4,3,4,5]$，最长严格递增子序列长度为 $3$，共有 $3$ 个。子序列按所选下标区分。

输入格式

第一行包含一个整数 $n$。

第二行包含一个整数 $x$。

第三行包含 $n$ 个整数 $d_1,d_2,\ldots,d_n$。

输出格式

输出两个整数，分别表示 $p$ 的最长严格递增子序列长度，以及这样的子序列个数对 $998244353$ 取模后的结果。

只需要对第二个数取模。

样例输入 1

3
3
1 -1 2

样例输出 1

3 3

样例输入 2

3
100
5 -3 6

样例输出 2

9 7

样例输入 3

3
1
999999999 0 1000000000

样例输出 3

2000000000 1

样例输入 4

5
34
1337 -146 42 -69 228

样例输出 4

1393 3876

数据范围

对于全部数据，$1\le n\le 50$，$-10^9\le x\le 10^9$，$-10^9\le d_i\le 10^9$。

令 $S=\sum_{i=1}^{n}|d_i|$。

提示

第一个样例已经在题目描述中说明。

第二个样例中，$p=[100,101,102,103,104,105,104,103,102,103,104,105,106,107,108]$。

第三个样例中，$p=[1,2,\ldots,2000000000]$。