sliniare

Se dă un vector $V$ de $N$ elemente din mulțimea $\{0, 1\}$. O subsecvență se numește liniară dacă egalitatea $aU - Z = b$ este adevărată, unde $U$ și $Z$ reprezintă numărul de elemente egale cu $1$ din subsecvență, respectiv numărul de elemente egale cu $0$ din subsecvență, iar $a$ și $b$ sunt numere naturale date.

Cerință

Să se determine numărul de subsecvențe liniare din vectorul $V$.

Date de intrare

Pe prima linie se găsesc $N$, $a$ și $b$ separate printr-un spațiu. Pe următoarea linie se găsesc $N$ numere naturale, separate printr-un spațiu, reprezentând elementele vectorului $V$.

Date de ieșire

Pe prima linie se va găsi un număr natural, reprezentând numărul de subsecvențe liniare din vectorul $V$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq a \leq 10 \ 000$
• $1 \leq b \leq 1 \ 000 \ 000 \ 000$

  #	Punctaj	Restricții
  0	0	Exemplele
  1	11	$N \leq 100$
  2	13	$N \leq 2 \ 000$
  3	17	Toate valorile din vectorul $V$ sunt egale cu $1$
  4	59	Fără alte restricții suplimentare

Exemplul 1

stdin

9 1 3
1 0 1 1 1 0 0 1 1

stdout

4

Explicație

Secvențele liniare sunt $[1, 0, 1, 1, 1]$, $[1, 1, 1]$, $[1, 1, 1, 0, 0, 1, 1]$ și $[1, 0, 1, 1, 1, 0, 0, 1, 1]$.

Exemplul 2

stdin

9 3 8
1 1 1 0 1 0 0 0 1

stdout

4

Explicație

Secvențele liniare sunt $[1, 1, 1, 0]$, $[1, 1, 0, 1]$, $[1, 1, 1, 0, 1, 0, 0, 0]$ și $[1, 1, 0, 1, 0, 0, 0, 1]$.

Exemplul 3

stdin

5 2 5
1 0 0 1 1

stdout

0

Explicație

Nu există nicio secvență liniară.