함수 $f(a_1, a_2, \dots, a_n)$은 배열 $a_1, a_2, \dots, a_n$의 비어 있지 않은 부분 구간의 원소 합 중 최댓값을 나타냅니다.

배열 $a_1, a_2, \dots, a_n$이 주어집니다. 동전 하나를 사용하여 $a$의 임의의 원소를 1만큼 감소시킬 수 있습니다. 또 다른 함수 $g(k)$는 최대 $k$개의 동전을 사용하여 얻을 수 있는 $f(a_1, a_2, \dots, a_n)$의 최솟값을 나타냅니다.

$g(1) + g(2) + \dots + g(k)$를 구하십시오. 이 값은 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 구하십시오.

입력

첫 번째 줄에는 배열 $a$의 원소 개수인 정수 $n$ ($1 \le n \le 100\,000$)이 주어집니다. 두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$)이 주어집니다. 세 번째 줄에는 정수 $k$ ($1 \le k \le 10^{13}$)가 주어집니다.

출력

$g(1) + g(2) + \dots + g(k)$를 $998\,244\,353$으로 나눈 나머지를 출력하십시오.

예제

입력 1

5
1 -1 2 -2 3
3

출력 1

5

입력 2

3
-3 -5 -35
1

출력 2

998244349

참고

첫 번째 예제에서 $g(1) = 2, g(2) = 2, g(3) = 1$입니다. 두 번째 예제에서 $g(1) = -4$입니다.