函數 $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$ 取模後的結果。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 100\,000$)：陣列 $a$ 的元素個數。

第二行包含 $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

說明

在第一個範例中，$g(1) = 2, g(2) = 2, g(3) = 1$。

輸入格式 2

3
-3 -5 -35
1

輸出格式 2

998244349

說明

在第二個範例中，$g(1) = -4$。