Supersecv

Avem un șir de $N$ numere. Cu toții știm că o subsecvenţă a şirului are forma: $(s_i, s_{i+1}, . . . , s_j )$ cu $1 \leq i \leq j \leq N$.
Scorul unei subsecvențe este dat de suma elementelor din acea secvență.
O K-Supersecvență este o secvență formată din $K$ subsecvențe adiacente ale șirului inițial. Scorul unei astfel de K-Supersecvențe este dat de suma scorurilor subsecvențelor din care aceasta este alcătuită.
De execmplu, pentru șirul $1, 2, 3$, avem următoarele 2-Supersecvențe:

• $\fbox 1 \ \fbox 2$ (de scor 3)
• $\fbox 1 \ \fbox {2 3}$ (de scor 6)
• $\fbox {1 2} \ \fbox 3$ (de scor 6)
• $\fbox 2 \ \fbox 3$ (de scor 5)

Două K-Supersecvențe se consideră distincte dacă diferă prin cel puțin una din subsecvențele din care sunt alcătuite.
Având un șir de numere, un număr $K$ și un număr $X$, trebuie să determinați câte K-Supersecvențe distincte cu scorul $X$ există în șir. Cum această cerință ar fi prea ușoară, fiecare dintre aceste K-Supersecvențe trebuie să fie formată doar din subsecvențe de lungime mai mare sau egală decât un număr $Z$ dat.

Date de intrare

Fișierul de intrare va conține pe prima linie un număr întreg $N$, reprezentând numărul de elemente din șir.
A doua linie conține șirul de numere.
A treia linie conține două numere, $K, X$ și $Z$, care au semnificația din enunț.

Date de ieșire

Fișierul de ieșire va conține pe prima linie un singur număr întreg, reprezentând numărul de K-Supersecvențe distincte cu scorul $X$ care există în șirul dat, fiind alcătuite din subsecvențe de minim $Z$ elemente, modulo $999 \ 983$.

Restricții

• $1 \leq K \leq N \leq 1 \ 000 \ 000$
• $1 \leq X \leq 1 000 \ 000 \ 000$

Punctare

• Pentru teste în valoare de $5$ puncte, $K = 1, N \leq 1 \ 000$ și $Z = 1$.
• Pentru alte teste în valoare de $5$ puncte, $K = 1$ și $Z = 1$.
• Pentru alte teste în valoare de $5$ puncte, $N, K \leq 15$ și $Z = 1$.
• Pentru alte teste în valoare de $15$ puncte, $N \leq 1 \ 000$ și $Z = 1$.
• Pentru alte teste în valoare de $50$ puncte, $Z = 1$.
• Pentru alte teste în valoare de $20$ de puncte, nu există restricții suplimentare.

Exemplul 1

supersecv.in

5
1 1 1 2 1
2 3 1

supersecv.out

4

Exemplul 2

supersecv.in

5
1 2 3 2 1
2 8 1

supersecv.out

6

Exemplul 3

supersecv.in

5
1 2 3 2 1
2 8 2

supersecv.out

2

Explicații

În primul exemplu, supersecvențele posibile sunt:
$\fbox 1 \ \fbox {1 1}$
$\fbox {1 1} \ \fbox 1$
$\fbox 1 \ \fbox 2$
$\fbox 2 \ \fbox 1$
În al doilea exemplu, supersecvențele posibile sunt:
$\fbox 1 \ \fbox {2 3 2}$
$\fbox {1 2} \ \fbox {3 2}$
$\fbox {1 2 3} \ \fbox 2$
$\fbox 2 \ \fbox {3 2 1}$
$\fbox {2 3} \ \fbox {2 1}$
$\fbox {2 3 2} \ \fbox 1$
În al treilea exemplu, supersecvențele posibile sunt:
$\fbox {1 2} \ \fbox {3 2}$
$\fbox {2 3} \ \fbox {2 1}$