Igor 有一个整数序列 $$$d_1, d_2, \dots, d_n$$$。当伊戈尔走进教室时,黑板上写着一个整数$$$x$$$。
Igor 使用以下算法生成序列 $$$p$$$:
1. 最初,$$$p = [x]$$$;
2. 对于每个 $$$1 \leq i \leq n$$$,他执行以下操作 $$$|d_i|$$$ 次:如果 $$$d_i \geq 0$$$,则他查看 $$$p$$$ 的最后一个元素(假设为 $$$y$$$)并将 $$$y + 1$$$ 附加到 $$$p$$$ 的末尾; 如果 $$$d_i < 0$$$,那么他查看 $$$p$$$ 的最后一个元素(假设为 $$$y$$$)并将 $$$y - 1$$$ 附加到 $$$p$$$ 的末尾。
例如,如果 $$$x = 3$$$,且 $$$d = [1, -1, 2]$$$,则 $$$p$$$ 将等于 $$$[3, 4, 3, 4, 5]$$$。
Igor 决定计算 $$$p$$$ 的最长递增子序列的长度及其数量。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。
如果 $$$a$$$ 的每个元素(第一个元素除外)严格大于前一个元素,则序列 $$$a$$$ 是递增序列。
对于 $$$p = [3, 4, 3, 4, 5]$$$,最长递增子序列的长度为 $$$3$$$,其中有 $$$3$$$: $$$[\underline{3}, \underline{4}, 3, 4, \underline{5}]$$$, $$$[\underline{3}, 4, 3、\下划线{4}、\下划线{5}]$$$、$$$[3、4、\下划线{3}、\下划线{4}、\下划线{5}]$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 序列 $$$d$$$ 的长度。
第二行包含一个整数 $$$x$$$ ($$$-10^9 \leq x \leq 10^9$$$) — 黑板上的整数。
第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$-10^9 \leq d_i \leq 10^9$$$)。
输出
打印两个整数:
- 第一个整数应等于 $$$p$$$ 的最长递增子序列的长度;
- 第二个应该等于它们的数量模$$$998244353$$$。
您应该只打印第二个数字模$$$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
注意
第一个测试用例在声明中进行了解释。
在第二个测试用例中 $$$p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]$$$。
在第三个测试用例中 $$$p = [1, 2, \ldots, 2000000000]$$$。