Codeforces Round 696 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

math

matrices

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. 1 2 3 4 ...

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIgor 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:

- initially, $$$p = [x]$$$;
- 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}]$$$.

Input

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

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 08:16:14 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|