Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Маца Јаца има за вас следећи задатак: Даће вам бројеве \(N, M\) а затим низ \(B = [B_1, B_2, \ldots, B_M]\), за сваки елемент важи \(1 \leq B_i \leq M\) (вредности бројева могу да се понављају). Ваш задатак је да формирате низ \(A = [1, 2, \ldots, N]\) (низ се индексира од \(1\)), а да затим, за свако \(i\) из низа \([0, 1, \ldots, N-M]\) (у растућем редоследу) урадите следећу операцију:

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

Другим речима, да за свако \(j\) почев од \(1\) до \(M\) (у растућем редоследу), вредност у \(A_{i+j}\) упишете у елемент \(A_{i + B_j}\). За крај, Јаца ће вам дати цео број \(C\). Ваш задатак је да израчунате вредност \(X = \sum_{i=1}^{N}(C^i \times A_i)\) по модулу \(998244353\) након свих операција.

Опис улаза

У првој линији стандардног улаза налазе се два природна броја \(N\) и \(M\). У наредном реду се налазе бројеви \(B_1, B_2, \ldots, B_M\), одвојени размаком. У наредом реду налази се један цео број \(C\).

Опис излаза

У једину линију стандардног излаза испишите тражени број \(X\) (\(0 \leq X < 998244353\)).

Пример 1

Улаз

14 6
6 4 3 3 2 1
-1

Излаз

16

Објашњење примера

Низ \(A\) ће након свих операција изгледати овако: ~~~ 1 5 1 5 1 5 1 5 1 5 2 2 5 1 ~~~

Ограничења

У свим тест примерима важи: \(M \leq N, -10^9 \leq C \leq 10^9\)