関数 $f(a_1, a_2, \dots, a_n)$ は、配列 $a_1, a_2, \dots, a_n$ の空でない連続部分列の要素の和の最大値を表します。

配列 $a_1, a_2, \dots, a_n$ が与えられます。 あなたはコインを1枚消費して、$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$ の要素数です。 2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$) が含まれます。 3行目には、整数 $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$ です。 2番目の例では、$g(1) = -4$ です。