Funkcja $f(a_1, a_2, \dots, a_n)$ oznacza największą sumę elementów niepustego podciągu spójnego w tablicy $a_1, a_2, \dots, a_n$.

Dana jest tablica $a_1, a_2, \dots, a_n$. Możesz wydać jedną monetę, aby zmniejszyć dowolny element tablicy $a$ o 1. Inna funkcja, $g(k)$, reprezentuje najmniejszą wartość $f(a_1, a_2, \dots, a_n)$, jaką można osiągnąć, wydając co najwyżej $k$ monet.

Oblicz $g(1) + g(2) + \dots + g(k)$. Ponieważ ta wartość może być bardzo duża, oblicz ją modulo $998\,244\,353$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 100\,000$): liczbę elementów w tablicy $a$. Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$). Trzecia linia zawiera jedną liczbę całkowitą $k$ ($1 \le k \le 10^{13}$).

Wyjście

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

Przykład

Wejście 1

5
1 -1 2 -2 3
3

Wyjście 1

5

Wejście 2

3
-3 -5 -35
1

Wyjście 2

998244349

Uwagi

W pierwszym przykładzie $g(1) = 2, g(2) = 2, g(3) = 1$. W drugim przykładzie $g(1) = -4$.