Maca Jaca ima za vas sledeći zadatak: Daće vam brojeve ~N, M~ a zatim niz ~B = [B_1, B_2, \ldots, B_M]~, za svaki element važi ~1 \leq B_i \leq M~ (vrednosti brojeva mogu da se ponavljaju). Vaš zadatak je da formirate niz ~A = [1, 2, \ldots, N]~ (niz se indeksira od ~1~), a da zatim, za svako ~i~ iz niza ~[0, 1, \ldots, N-M]~ (u rastućem redosledu) uradite sledeću operaciju:

for (int j=1; j<=M; j++)
  A[i + B[j]] = A[i + j]

Drugim rečima, da za svako ~j~ počev od ~1~ do ~M~ (u rastućem redosledu), vrednost u ~A_{i+j}~ upišete u element ~A_{i + B_j}~. Za kraj, Jaca će vam dati ceo broj ~C~. Vaš zadatak je da izračunate vrednost ~X = \sum_{i=1}^{N}(C^i \times A_i)~ po modulu ~998244353~ nakon svih operacija.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se dva prirodna broja ~N~ i ~M~. U narednom redu se nalaze brojevi ~B_1, B_2, \ldots, B_M~, odvojeni razmakom. U naredom redu nalazi se jedan ceo broj ~C~.

Opis izlaza

U jedinu liniju standardnog izlaza ispišite traženi broj ~X~ (~0 \leq X < 998244353~).

Primer 1

Ulaz

14 6
6 4 3 3 2 1
-1

Izlaz

16

Objašnjenje primera

Niz ~A~ će nakon svih operacija izgledati ovako:

1 5 1 5 1 5 1 5 1 5 2 2 5 1

Ograničenja

U svim test primerima važi: ~M \leq N, -10^9 \leq C \leq 10^9~

• U test primerima vrednim 10 poena: ~N, M \leq 10000~.
• U test primerima vrednim 60 poena: ~N \leq 500.000, M \leq 100.000~.
• U test primerima vrednim 30 poena: ~N \leq 20.000.000, M \leq 100.000~.