시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

The function $f(a_1, a_2, \ldots, a_n)$ represents the largest sum of elements on a non-empty subsegment in the array $a_1, a_2, \ldots, a_n$.

You are given an array $a_1, a_2, \ldots, a_n$.

You can spend one coin and decrease any element of $a$ by $1$.

Another function, $g(k)$, represents the smallest value of $f(a_1, a_2, \ldots, a_n)$ you can achieve by spending at most $k$ coins.

Find $g(1) + g(2) + \ldots + g(k)$. As this value may be very large, find it modulo $998\,244\,353$.

입력

The first line of input contains one integer, $n$ ($1 \leq n \leq 100\,000$): the number of elements in $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \leq a_i \leq 10^8$).

The third line contains one integer $k$ ($1 \leq k \leq 10^{13}$).

출력

Print $g(1) + g(2) + \ldots + g(k)$, modulo $998\,244\,353$.

예제 입력 1

5
1 -1 2 -2 3
3


예제 출력 1

5


예제 입력 2

3
-3 -5 -35
1


예제 출력 2

998244349


힌트

In the first example, $g(1)=2, g(2)=2,g(3)=1$.

In the second example, $g(1)=-4$.