F. 1 2 3 4 ...
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Игоря была последовательность $$$d_1, d_2, \dots, d_n$$$. Когда Игорь зашёл в класс, на доске было записано число $$$x$$$.

Игорь создал последовательность $$$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]$$$.

Игорь решил посчитать длину наибольшей возрастающей подпоследовательности $$$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, \underline{4}, \underline{5}]$$$, $$$[3, 4, \underline{3}, \underline{4}, \underline{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$$$ надо выводить только второе число.

Примеры
Входные данные
3
3
1 -1 2
Выходные данные
3 3
Входные данные
3
100
5 -3 6
Выходные данные
9 7
Входные данные
3
1
999999999 0 1000000000
Выходные данные
2000000000 1
Входные данные
5
34
1337 -146 42 -69 228
Выходные данные
1393 3876
Примечание

Первый пример разобран в условии.

Во втором примере $$$p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]$$$.

В третьем примере $$$p = [1, 2, \ldots, 2000000000]$$$.