CF1474F 1 2 3 4 ...

Igor had a sequence $ d_1, d_2, \dots, 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 \leq i \leq n $ he did the following operation $ |d_i| $ times: - if $ d_i \geq 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}] $ .

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the length of the sequence $ d $ . The second line contains a single integer $ x $ ( $ -10^9 \leq x \leq 10^9 $ ) — the integer on the blackboard. The third line contains $ n $ integers $ d_1, d_2, \ldots, d_n $ ( $ -10^9 \leq d_i \leq 10^9 $ ).

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 $ .

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, \ldots, 2000000000] $ .