函数 $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

输入格式 2

3
-3 -5 -35
1

输出格式 2

998244349

说明

在第一个样例中，$g(1) = 2, g(2) = 2, g(3) = 1$。 在第二个样例中，$g(1) = -4$。