La fonction $f(a_1, a_2, \dots, a_n)$ représente la plus grande somme des éléments d'un sous-segment non vide du tableau $a_1, a_2, \dots, a_n$.

Vous disposez d'un tableau $a_1, a_2, \dots, a_n$. Vous pouvez dépenser une pièce pour diminuer n'importe quel élément de $a$ de 1. Une autre fonction, $g(k)$, représente la plus petite valeur de $f(a_1, a_2, \dots, a_n)$ que vous pouvez obtenir en dépensant au plus $k$ pièces.

Calculez $g(1) + g(2) + \dots + g(k)$. Comme cette valeur peut être très grande, calculez-la modulo 998 244 353.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 100\,000$) : le nombre d'éléments dans $a$. La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$). La troisième ligne contient un entier $k$ ($1 \le k \le 10^{13}$).

Sortie

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

Exemples

Entrée 1

5
1 -1 2 -2 3
3

Sortie 1

5

Entrée 2

3
-3 -5 -35
1

Sortie 2

998244349

Remarque

Dans le premier exemple, $g(1) = 2, g(2) = 2, g(3) = 1$. Dans le second exemple, $g(1) = -4$.