Hàm $f(a_1, a_2, \dots, a_n)$ biểu diễn tổng lớn nhất của các phần tử trên một đoạn con không rỗng trong mảng $a_1, a_2, \dots, a_n$.

Bạn được cho một mảng $a_1, a_2, \dots, a_n$.

Bạn có thể chi tiêu một đồng xu để giảm bất kỳ phần tử nào của $a$ đi 1.

Một hàm khác, $g(k)$, biểu diễn giá trị nhỏ nhất của $f(a_1, a_2, \dots, a_n)$ mà bạn có thể đạt được bằng cách chi tiêu tối đa $k$ đồng xu.

Hãy tìm $g(1) + g(2) + \dots + g(k)$. Vì giá trị này có thể rất lớn, hãy tìm nó theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 100\,000$): số lượng phần tử trong $a$.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Dòng thứ ba chứa một số nguyên $k$ ($1 \le k \le 10^{13}$).

Dữ liệu ra

In ra $g(1) + g(2) + \dots + g(k)$, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

5
1 -1 2 -2 3
3

Dữ liệu ra 1

5

Ghi chú

Trong ví dụ đầu tiên, $g(1) = 2, g(2) = 2, g(3) = 1$.

Dữ liệu vào 2

3
-3 -5 -35
1

Dữ liệu ra 2

998244349

Ghi chú

Trong ví dụ thứ hai, $g(1) = -4$.